Smashing Magazine expound upon what makes a well designed 404 page in their latest design gallery which features 50 examples.
Inspired by the gallery, I made a more useful 404 for Konigi as well.
http://www.smashingmagazine.com/2009/01/29/404-error-pages-one-more-time/