You need to start with something small, simple to automate, and high value.  Pull down some sweet, low hanging fruit, and you will be able to sell the process.  Show how it saved someone a late night or a weekend call.  Then you can expand out from there.  

To do automated testing well, you need someone who is a resource and an evangelist, and who has buy in from higher level managements.