The first thing you need is to have meta keywords in the pages. The solution I discovered for doing this is the All In One SEO Pack, this automatically makes the categories of a blog post become meta keywords, allows adding arbitrary meta keywords when editing the blog post, and supports keywords for the entire blog. It also re-writes the titles to have the title of the post appear before the title of the blog in the <TITLE> tag which is rumored to be a good thing to do.
The next thing you want to do is to create a Google sitemap. A sitemap is an XML file that describes all the URLs in your web site which tells Google (and other search engines) the last change dates of all the URLs and the change frequencies (or how often they should be checked for changes). Note that the format is called Google Sitemaps because Google invented it, other web search engines also use the same format. To generate my sitemap I use the Google Sitemaps Generator which tells earch engines to index my main blog page daily and the category pages weekly (which is configurable). It also has an option to notify Google of changes by pinging the Google service.
Having multiple names for the same web page hurts you when it comes to search engines. Having two separate pages at the top of page 2 is not nearly as good as having one page on page one! To solve this problem I use the Permalink Redirect plugin to make sure that each page has only one URL pointing to it. This plugin also allows redirecting the feed URL to feedburner.com. Feedburner serves the feed data (thus saving you some bandwidth if you are on a slow link) and also tracks statistics on it which are interesting.
Under the Writing section of the Options menu there is an option to enter a list of URLs for update services that can be notified of every post. I use http://rpc.pingomatic.com/ and http://rpc.technorati.com/rpc/ping. The Update Services entry in the WordPress Codex has more information on how this works.
Social networking sites such as digg.com can direct a large amount of traffic to your site if you write about a popular topic. The Share This plugin is the simplest way I found of adding social networking hooks to WordPress (I tried a few others that had both less functionality and less ease of use).
Finally before publishing a post, I often check the Google Adwords Keyword Tool. This often gives me ideas on how to make the meta tags and title match what people are searching for.
There’s actually a really great way for generating a sitemap of your wordpress blog:
http://wordpress.org/extend/plugins/google-sitemap-generator/
It knows about the layout of wordpress and can therefore more accurately represent your site.
Luke, isn’t that the same sitemap generator I referenced in my post?