Nene, there are a number of places you can learn more about search engine marketing, educating yourself will safeguard you against scams out there. Submissions to search engines are no longer needed is correct, links pointing back to your individual web pages are how the search engines find your website or blogs nowadays. If you use website analytics the reports generally show the majority of your traffic will come from Google. If a company is not willing to tell you everything they will provide step by step in the search engine marketing project you need to look at another company for services.
Here are a few places you can research to learn more about search engine marketing. You should also get an idea from these places who the well known search engine marketing companies are if you hang around long enough or learn enough to do the work yourself in-house:
http://www.highrankings.com/forum/
http://www.webmasterworld.com/
http://www.searchengineland.com/
http://www.forums.searchenginewatch.com/
http://www.sphinn.com/
allenpassafaro, search engines see inbound links like a vote of confidence from another website to your website. There are all sorts of variables the search engines use to evaluate a link pointing back to your web page so its not easy to understand exactly what the search engines want. Search engines suggest inbound links should be on topic or closely related to the same topic your site or blog is about. Links work for individual pages not websites, a link pointing to a page give that individual page value through the inbound link so you need links for all your important pages on your website. Quality inbound links in my experience really help a website with link popularity for long term search results. Also the more authoritative a website is that links back to you the more important the search engines think that link is in terms of value.
Linking can be pretty complex to understand so I would recommend learning more about inbound links at a few of the sites listed previously in this post.