The company who is going to "promote" the site up is an SEO business. This are effective, but risky.
They use questionable techniques (comment spam, gateway pages etc...) to get more links to your site around the net, in turn increasing your page-rank in google.
However... this is against google regs, and they could pull your listing completely (including all adwords links!) totally killing your business stream.
I suggest doing it yourself.
1. Use adwords effectively (as mentioned by many people above). Run several campaigns at once, track conversion and sales. People might click the ad but not purchase, try to find out why. Could be poor navigation, difficult purchase process or one of a million other things. Increasing the conversion % will bring more business immediately with no cost. It is important do this first to gain the most value from additional marketing spend
2. Make sure your site is search optimised. There is a load of stuff on the net about this. As a summary, keyword rich text, proper meta tags (descriptions and keywords), alt tags on images, full sitemap (with sitemap xml, you can submit this via google webmaster tools to help them index your site), XHTML compliance (helps the crawlers), load more info on various SEO blogs and sites.
3. Get information about your site out there and talked about. Forums, newsgroups, well known industry sites. The more places your site is linked from and the more credible those places are, the higher your page rank.
SEO work is pretty easy to do yourself (or within your business) without resorting to underhand techniques. But nothing will increase your sales like increasing your conversion rate. Try multiple landing pages, adding PayPal acceptance, removing any signup barrier to purchase, free delivery etc... If you double your conversion rate, and additional marketing doubles your traffic, you have increased your sales by x4.
Best of luck!