Here are some WordPress plugins that you should have if you’re interested in SEO.
(Not all are strictly directly SEO-related but the ones that aren’t can still help you gain a wider readership; gaining natural links and increasing your blog’s usefulness as an SEO tool!)
All In One SEO Pack – the must have for all SEO fanatics, allowing you to optimise titles and automatically generate meta tags.

Automatic SEO Links – easily able to set the link title, target and rel of all your links from the WordPress CMS.
flickrRSS – allows you to import your flickr images into your blog, getting useful title and alt attributes in there.
Automatic Youtube Video Posts – automatically creates a post for Youtube videos including description – useful way of creating content.
SEO Friendly Images – automatically add alt and title attributes to images.

Google Sitemap Generator – automatically generates an XML sitemap for your blog.
Permalink Trailing Slash Fixer – adds a trailing slash to your category-level posts.
Sociable – allows others to easily promote your posts through social bookmarking sites.
PS Auto Sitemap – generate an HTML sitemap for your blog.
TweetMeme Retweet Button – keep track of the links you gained from twitter and allow people to tweet your ramblings.
SEO Slugs – Removes unnecessary words from permalinks.
Twitter Tools – integrate your WordPress and Twitter accounts. Get your posts out into real-time search and tweet from WordPress.

Redirection – keep track of 404 errors and easily implement 301 redirects.
Pretty link – provides you with your very own URL shortening service.
SphinnIt – let people promote your SEO blog posts in the sphinn world!
Let me know if you have anymore to recommend!

Nice list! Thanks for sharing
I am not sure if you can consider flicker and youtube plugins to be SEO plugins though
The robots meta plugin by Yoast is also an essential one for WordPress SEO. It allows you to control exactly what Google will index, which isn’t an easy thing to do with WordPress otherwise.
I like the way you can be really particular about which links you want to be dofollow and nofollow in order to stop unecessary PR leakage across your blog as well.
Direct link here - http://yoast.com/wordpress/meta-robots-wordpress-plugin/