1st, define and pencil design your framework (to the best of your ability at the time).
2nd, if your AUT is not ready, begin fleshing out your framework and writing the initial code that you can (i.e. if your AUT is web based, write your DOM interaction code like load IE, navigate, push buttons, fill out text boxes, etc...) Your framework should be independent from your AUT automation.
3rd, define what your (your boss') priority is for what gets automated and when.
4th, define if you want to do broad & shallow (smoke test) or deep & targeted (regression test) type of automation first.
5th, define your goals and timetable for deliverables so your boss will know how to measure your progress.
Depending on how big your application is and the build cycles you go through, you might want to take consideration in how many versions you are planning on using and what Configuration Management you will implement to keep track of your scripts. Larger application development programs may have multiple functionalites being developed at the same time, but in separate areas and then merged together into a third area. Are you going to test each one separately and then together or just one at the end? Will the approach limit time for bug fixes within the development lifecycle if you are only testing at the end? The larger the application being developed, the more a test engineer will need to take a program management and full life cycle scripting approach.