What Planes and ampie_salehoo said. Dead On!
Start at google, they tell you what to do and they even have videos on Youtube. Sign up for their webmaster tools and read carefully. They tell you what not to do.
Then focus on creating backlinks back to your main site based on the related keywords. If your site is about selling blue widgets, then join a community about blue widgets and contribute useful information. Of course in those posts, your user name can be your store name and you can promote your site in your signature when it's relevant.
I'd resort to Adwords as a last resort unless your competing in a high traffic arena. There are tools out there for free that will let you scope out your competition. keywordspy.com is one that will let you do 20 free searches to see what your competitors are using and paying on. Theres so much more.
Don't get caught up in paying for information unless you're really really stuck. This stuff is fairly easy to compete in, partly because not very many people are optimized properly. They just put up a site and submit it to google and think that's going to make them money.
Create a site map, make effective use of your headers and pate titles, make sure your content is relevant. don't cloak or do anything that the google videos tell you not to do. Play nice with other communities that your product revolves around, the credible ones will get your site exposure for free as well as higher rankings in time. Keyword is TIME.
Don't get suckered by companies or SEO optimizers that promise immediate results, because you will be banned from google in no time, it's a hassle to get back in their good graces as you'll see in their webmaster tools videos.
There's more caveats out there, but really... the good path to follow is already posted here by others in this thread.
Good luck.