"We will submit your website to hundreds of search engines!" sounds like a scam. It is. According to NetMarketShare, Google has 79% of the search market. In some countries it's a lot higher. Second is the Chinese search engine, Baidu on 11%. Then we have Yahoo on 6% and Bing on 3%. That adds up to 99% of the search engine market. The biggest player in the tiny bit remaining is Ask.
So, whilst it is true that there are hundreds of other search engines, virtually nobody is using them. OK, there's a few that may be be important in specific geographies - like Yandex in Russia, for example.
Yahoo search results are now supplied by Bing: if you can get listed in Bing, you will be listed in Yahoo. So to get 88% coverage - or more if you ignore the huge Chinese market - you just need to submit to Google and Bing.
If you don't want to ignore the huge Chinese market, Baidu has a submit page but when I recently created a brand new site the Baidu spider came to index it without any invitation from me, even though there were no other sites linking to it. I'm guessing it's somehow monitoring domain name registrations or DNS changes. All my older sites are listed, even though I've never done anything to submit pages to Baidu.
So how to get listed in Google? Sign up for Google Webmaster Tools and click the big red Add a Site link. To take full advantage of all the useful information that Webmaster Tools offers you will need to verify that you own the site. Google supplies a tiny XML file that you upload to your website and then you just tell Google it's there. It's all explained once you're registered.
To do the same for Bing (and therefore Yahoo) the process is virtually identical. Sign up for Bing Webmaster Tools - name sound familiar? The Bing Add Site button is blue and Bing supplies a tiny XML file that you upload to your website and then you just tell Bing it's there. It's all explained once you're registered.
Now you should get spidered by the world's largest search engines and your fortune is made. Well maybe not, but you've certainly saved some money by not signing up for some "We will submit your website to thousands of search engines!" program.