Yet Another Related Posts Plugin is easily the best related posts plugin out there for WordPress, especially after a recent update that makes it easy to use templates to determine the exact look and feel of the output. It also speeds things up a bit by giving the user the option to cache the related posts SQL output.