SEO is a tedious and very difficult process and there really is no quick fix. There are a lot of companies overseas that offer inexpensive services, but most use techniques that can get your site blacklisted (no matter what they claim). The firms that do it right are very expensive. You can do it on your own if you get a real handle on titles, tags, style sheets, keywords and keyword density, but even that is just the beginning.
Amazon's fulfillment services aren't a bad way to go. If you use their services, your products will be eligible for Amazon Prime, which will increase your exposure and help you sell more. Amazon does take a hefty cut though. Also, getting on with Amazon as a gold seller isn't the easiest thing to do, and the spreadsheets ... it took us a couple of weeks with an Excel professional to get up and running with them.
Just to add to what Mr. Shepherd said, there are no quick fixes to SEO and SEM. Until recently, I was the Director of IT Services at multi-million dollar-a-year company with a departmental budget of $750,000, for the last 5 years.
For a business just starting out, I would not recommend using any company that promoted any guarantee of getting your business to the top of the SERPs (Search Engine Results Pages). In the early days of the internet, promoting your site and getting it to rank was dead-easy because everyone was still learning how the internet should function. Today however, the internet is very much user driven...meaning that Search Engines (like Google) pay close attention to what the average person expects to experience...and the search engines have responded during the last two-years with multiple upgrades that have been a benefit to many sites, but killed many more (blacklisted).
The best approach to getting your website to rank well (in the beginning), is to not worry about ranking at all. Write the content of each page as if it were a conversation you were having with a person right in front of you. From that point, you would make slight refinements to the content until it's perfect. Well written, original content, that serves a purpose to the people visiting the page will always continue to rank higher and higher over time. I would suggest starting out by visiting the Google, Bing and Yahoo web developer pages as they all very specifically list the types of things to avoid when building your website. Once you have well written, original content on your site, you would then move forward to SEM (online advertising).
There are some key differences though between an informative site and a commerce site which also plays an important role in natural ranking, but I don't want to get into that presently as I might derail this thread.
If there is interest on Pearl-Guide, I'd be more than happy to share my more than 12 years of IT experience in a new thread titled as such - or anyone is welcome to msg me.