Visitors most commonly use a search engine to find Web sites. Research shows that a whopping 80% of first-time visitors find Web sites using Search Engines. Keep an eye on http://www.searchenginewatch.com and http://www.statmarket.com to determine which search engine is currently the most popularthe popularity of search engines changes on an almost daily basis. However, Google (http://www.google.com) and Yahoo! (http://www.yahoo.com) are usually pretty high up in the list, and AOL is currently perceived to have the highest conversion rate of referrals to orders.
When adding your site to a particular search engine's listing, carefully read the instructions for that particular search engine. Each has its own way of determining how your site will be listed and found, especially if you are using its free submissions service.
Usually, the search engine staff checks each submission of the paid services, but no checks are made of free submissions. If you entered some information wrongly, any mistakes will more likely be rectified if you paid for the service.
In general, it is worth paying for the paid submission services because they are much faster (often 24 to 48 hours to be included, as opposed to several months for free services), and your site is much more likely to get accepted into the listings that way.
Be aware that you should check your position with the search engines regularly because they often change their algorithms for determining which sites rank highest. This can have a drastic affect on your positioning. The recent Google Florida Update change was particularly drastic and affected many sites' positions dramatically.
A number of useful tools can help you submit Web sites to many search engines in one go. Among them is Web Position Gold, which I can recommend. A good source of tools of this kind is http://www.download.com.
Always, always, always add your site to http://www.dmoz.org, the Open Directory Project, a directory of the Web. So many people forget to do this or opt not to because the speed with which a Web site is added to the directory cannot be guaranteed, and it can take months. However, once your site is on here, it is guaranteed to appear in lots of search engines all over the Web. The Open Directory powers the core directory services for the Web's largest and most popular search engines and portals, including Netscape Search, AOL Search, Google, Lycos, HotBot, DirectHit, and hundreds of others. Similarly, Overture/Inktomi, another highly recommended service, is the core directory service for Yahoo!, About, HotBot, and MSN.