Let me clear up a few things here.
Yahoo has a brand new search engine that uses Inktomi and Overture results. They have dropped Google completely.
You can no longer submit to Inktomi or AlltheWeb, as Yahoo has dumped them into a new program at Overture called Site Match that fuses paid inclusion and pay per click together (so you have to pay twice).
The rumor is that AlltheWeb and AltaVista will soon disappear, eaten by Yahoo.
Google uses a lot of smaller directories and search engines, including DMOZ. DMOZ is not doing too well right now because the volunteer editors are getting too far behind. It also seems to be having server problems.
Google is still free, except for the AdWords and AdSense advertising campaigns.
The key to good positioning on the search engines is having excellent meta tags and keywords in your content. And, submitting your site to ALL relevant search engines and directories. They description and keywords tags do not have to be on every page, unless you are selling products.
I disagree with Stargal in that why bother learning SEO when there are people like myself who do nothing but SEO all day long? You web developers and designers (and business owners) have enough to do without having to learn a whole new field.