I've found that the search engines that matter will find your site without submission. Less than a month after setting up my hosting web site it was indexed by Google, AllTheWeb, Altavista, Lycos, Vivisimo, and several others. These companies might have agreements with domain name registrars and then get updates when ever a new domain name is registered. Either that or they comb unindexed IP addresses.
It helps if your site has high availability (Google will drop you from their index if you are unreachable), and if you are content heavy. Also forget about search engine meta tags.
Well formed (x)html with context clues, such as appropriately using lists and tables helps too from what I hear.
-Paul