This is the advice we give to our customers when they ask and it does work well, as we have had success with it:
1. Page titles are very important. Make sure your page title is descriptive. E.g. "Home" is not good. "(Company Name) - Offering the best in (whatever you do) - (section name)" is better - e.g. "MacHighway - Mac Friendly and Mac Compatible Web Hosting, Email and eCommerce - Support".
2. Text. Lots and lots of it talking about what you do. Google does not index the words in images. The higher up on the page the text is the more important it will be weighed. A standard "inverse pyramid" style of writing is effective. The way news articles are written with the most important elements at the top.
3. Links - get other people to link to your site. The more sites that link to you, the more important your site will be and the higher it will appear in Google's rankings.
4. Straightforward site structure - this another place where page titles are helpful. If you look at my company's listing in Google (search for "MacHighway") you will see that it has an enhanced listing where several of the sites sections have their own link under the result. This is done manually by Google staff. The more straightforward your arrangement and page titles the more likely you are to get an enhanced listing. (it will take time however)
5. Don't give up on Meta tags - just make sure your keywords are actually appropriate to your site. If you "stack" your meta tags it can actually hurt your listing.
I may be leaving something out, but I think that covers it. As for AdWords - it can be effective. The more people wanting the keywords you have the more expensive it can be. I'd use it in conjunction with Google Analytics - that way you can see what keywords visitors are already using to find your site, and helps you track how much traffic your ads are bringing you so you can fine tune your approach. It's a nice system.