From this WebWord entry (via their mailing list) is this surprisingly helpful page on creating good 404 pages:
Offer a link to the site map, or better still, reproduce the site map on the error page. This will help those users that might have been just looking for a particular section, say, the “Services” page. […]
I like to use http://fastolfe.net/features/perl/#404.pl