Don't ever be taken in by search engine submission services that will submit your site to thousands of quality search engines and directories - there is no such thing. MSN, Google and Yahoo are responsible for driving over 90% of search traffic! This makes things a little easier, but search site relationships change all the time and where do you have to be to do well on those three?
Let's start with Google: Google is a search engine that uses a spider. You can submit your site to Google using their free submission service. It's probably better to let Google find your site on its own though. Or help the process by placing a link to your site on another site that is being spidered by Google (in a relevant way of course). Google uses DMOZ or the Open Directory Project for its directory results. DMOZ is a directory that uses volunteer editors - it can be a chore to get listed there but will be worth its weight in gold.
Google uses their own PageRank system. PageRank is based on popularity and site content. Popularity comes from links coming to and going from your site. These links to other sites should be relevant to your content, and if you decide to link to another Web site, it might be a good idea to ensure that the site has a PageRank (and not a greyed out or 0/10 rank indicating a Google "issue). To see a site's PageRank, download the Google Toolbar for your browser.
Use the Webmaster Resources to add a Google SiteMap to your site that will assist Google when spidering the site. Even if you don't do that, go ahead and get your site verified so that you can get access to some free analysis from Google on your site, your robots.txt and spider activity.
And on to MSN: MSN has their own search engine, and search engine spiders. MSN offers a free submission. MSN's algorithm is different than Google's, and you will find very different results.
Yahoo: Yahoo has a free submission - setup an account at Yahoo and then browse to the directory to where your site should be. Find the link to suggest a site, and you should also find the link to submit the site for free to their search engine. Yahoo suggests that you use Yahoo Search Marketing Site Match, which means that you must pay-per-click. For those on a tight budget, this may not be possible. But try the free submit and see where you end up.
Yahoo has added some services to help you determine more about your site, like Site Explorer which is still in Beta.
Resources:
Search engine submission links:
DMOZ (the open directory project)