I usually start with an SEO audit of the top ranking phrases on Google (backlink analysis, domain age, site indexing, PR, and so on) I might also do some PPC research (identifying the most sought after keywords - most expensive CPCs, and also looking at a range of related industry terms to see how much people are paying for them) What else is worth looking at?
Use tools from Overture, wordtracker as well, finalise set of keywords to target. And rest of SEO like, preparing content, page optimization etc