I may suggest the following approach:
1) Define the primary/secondary target for automation. For example we decided that primary target should be BVT execution on any new build made, prior to introduce it to whole QA. Next is to automate most rutine test cases. Third is to automate regression testing.
2) Second and not less important is to understand what kind of tool you need and will your management approve it. We are using Rational tools and it works.. but there is a problems with support