Her's my patented recommendation for approaching Automation:
First determine if you product is stable and ready for automation. There are many past discussions on QA_Forums, just use the old search button at the top. Also insure you have well written and documented manual test cases to provide as close to full coverage as possible.
Then get your testers together along with your immediate manager and do a brainstorm on the requirements needed for a tool. Then put together a Planning and Scope document of your proposals and get buy-in from senior management. Take your requirements list and formalize it then send it to the Vendors of the tools which you think might be applicable for you. Once you have a list of tools, do your own evaluation on the tools, which will require you obtain demo copies of the tools. If you can not get them, they are probably not the tools you want. Ask Vendors for references, contact the customers to see how they use and like the tool. Ask any that might be local, about an on-site demo of how they are using it. Finally have the Vendor do a proof of concept. This might cost you, but it's better than having useless shelfware when you abandon the tool because "it just doesn't work for you".
And last, but not least, hire a tool skilled or certified contractor(commercial or independent), to get you up and running with a suite of scripts that are well documented and insure that he passes on the valuable hints and tips of the tool usage.
Remember automating is development and must be budgeted and planned for similarly.
Success is the ability to go from one failure to another with no loss of enthusiasm.
~ Winston Churchill ~