Just a quick note on submitting. I haven't bothered submitted anything to any of the major search engines, since late summer 2001. If you work on getting linked into the community of related websites, you'll get found and crawled without submitting or paying.
There are only a few "major" crawling search engines left:
1. AllTheWeb (formerly owned by FAST, now owned by Overture)
2. Altavista (now owned by Overture, probably going away soon)
3. Google (owned by... Google!)
4. Inktomi (now owned by Yahoo)
Beyond these, MSN has a new experimental spider crawling the web, which will probably end up driving part of their search results one day. Looksmart has Wisenut.com's "Wisebot" crawling. Ask.com has Teoma crawling the web. All of them will find your site on their own, if you work on building up links from other sites.
An article you might want to check out, a bit dated in terms of who owns which crawler, but the strategy is still the same:
http://www.webpronews.com/articles/1111dthies.html
When I launch a site, I work on a few key link partnerships early on, so the links go live the day the site launches. We normally get crawled by all the spiders within a couple weeks. Submitting (other than paid inclusion) does not appear to speed this up at all, and might even slow things down.