SEO in a nutshell
I just posted this advice on a forum, and remembered my long-forgotten blog. Not exactly revolutionary stuff, but here are some basics on how to get the search engines to rank a site well.
Last time I looked, Google hadn't indexed this blog at all, let alone given it a good ranking... so maybe my advice on SEO should be taken with a barrel-load of salt!
Finding keywords and keyphrases
Decide on the words and phrases that you want to appear at the top of the search-engine results for. Use a service like wordtracker.com to help in this process: you may find closely related words / phrases that more people search for, if so you want these as your keywords too.
Putting all the keywords and keyphrases on your site
Make sure all the keywords and keyphrases you identified above are on your site. Make sure the most important ones are in title and h1 tags as well as in body text. Remember that people have to read your site as well as search engines, so don't go overboard!
Don't do anything dodgy
Search engines can lower your ranking if they detect that you're trying to spam them with cheap SEO tricks. So don't do anything late-90s like sticking keywords in white text on a white background, or serving up different content to robots. Be careful not to have multiple sites or pages with significant duplicate content (e.g. 80% or so same body text) - one of them will probably be largely ignored by the search engines, and there's a chance that both will be. Similarly don't duplicate anyone else's content: Google etc. look for this sort of thing.
Get links from relevant sites
Try to get in directories like dmoz.org - best of luck there ;-). If you have a "commercial" site, you'll find matters more difficult - lots of the important directories will want to charge you.
Contact the administrators of sites in a related field that look like they might link to you, and try to talk them into it. Focus on the ones that are doing well in the search engines themselves. You can use Google Pagerank to get an idea of this (download the official toolbar or a Firefox extension like Google Pagerank status - I like this one). Before putting too much persuasive effort into a site, make sure that the page that they'd put your link on has good Pagerank: Pagerank gets distributed from one page to another as described here.
Some sites have link pages that don't get indexed by the search engines (because they use some peculiar dynamic URL system, or because it's specified in their robots.txt file), so they're no use to you for SEO. You may of course get people clicking the links in those pages, so if it's a popular site it may be worth trying to get them to link to you anyway.