This is a loaded question and the answers above are a great start but there is a lot here. Having a beautiful site is like having a billboard in a cornfield. It's pretty but no cars are driving past.
You must get your billboard on a freeway and Google is one of the biggest ones.
1. Set your keywords - Google uses these to decide which keyword "file folder" they should go in.
2. Set your meta descriptions - Google uses this text to show below your page listing in a search result. These should match your keywords also.
3. Set your title - Again this should match your keyword focus for the page.
If your titles, keywords, or descriptions aren't focused on one specific keyword phrase, then that's telling you that you need more pages "beneath" this one... meaning more subcategories, etc.
What this builds is a page hierarchy or a genealogy. Once you have your genealogy in place and NOP Commerce has done it's job you're just about at the limit of what NOP is going to do for you.
Now you need to:
1. "Control your juice". If your website is a genealogy tree with the trunk pointing up... imagine search engines "pouring" traffic (or juice) down into it. This juice should flow only down to branches that are important and focused. You need to now selectively use NOFOLLOW tags on anchor text to channel the right juice into the right branches. NOP by default doesn't support this, but with a very simple mod to your category navigation module, you can ensure that parents link to children and children link to parents, but no cousins link to cousins. That's good advice in real life as well for those of us in the deep south :) (I'm in Florida)
2. Flesh out every product page with attention to your specification attributes... these wil guide your keywords pretty specifically.
3. Announce your pages to as many external backlink sites as possible. This doesn't mean link spamming (ugh). But don't fall prey to linking everything to your homepage... You should Facebook, Tweet, Index, Catalog, and otherwise get every web directory and external site and message forum to link to thousands of your highly specific deep-link pages. The rumor that deep linking is bad couldn't be more wrong. Your homepage is ranked on the cumulative PR value of its grandchildren... not it's raw PR ranking itself.
4. Syndicate your product data beyond Froogle. You should be in Amazon, Yahoo Shopping, NexTag, Bizrate, Shopping.com and more.
5. Advertise your product specific pages with distinct Google Adwords campaigns. This costs money but if you target 3-4 word phrases it's relatively cheap (<$0.25 per click). Don't start out with the big words (1 word competitive phrases) or you'll be dying on the $8 per click vine and you'll think that advertising doesn't work.
6. Film videos of your products in use. People don't buy products.. they buy what a product does for them. You don't buy soda because it's 16 fl oz. in a red can... you buy soda because by drinking it, women will be attracted to you and you will have large muscles. Video is one of the best ways to convey the "benefits" of your product rather than the "features" of the product.
7. Write great product descriptions. Don't fall prey to vomiting up what your product "is" in your product description... describe what the product does for the customer in your product description (while still including keywords).
By far NOP is the top commerce platform that I've seen, but don't think for a second that just by posting your website and sitting on the hill that the crowds will gather. Now it's time to go to market!
I hope that's helpful. I have a 20 page writeup on all the techniques that I've used for stores like the Yahoo! sports shop (sports.yahoo.com) among others.. Let me know if it's helpful to you.
Customer Objectives Whitepaper -
Web version -
PDF versionJared Nielsen
www.FUZION.org