I had seen a couple of "Related Posts" implementations for WordPress and other blogs and they did not really make much sense to me. Once I had the code for contextual searches, the related posts plugin was a simple extension of that search code.
This plugin has the following features:
-related posts from your own blog, so more linkage
-extremely customizeable output
-links listed according to relevance
-"fuzzy" matching of posts/titles
-very easy install
You can see an implementation of this on http://weblogtoolscollection.com . Just click on the permalink of any entry and look for the titles at the bottom of the post content.
Download the plugin from here:
Please post bugs.