Jeff Atwood rants about the typical 404 page, saying "the average internet user has no idea what 404 means or what to do about it. To them, it's yet another unintelligible error message from the computer. Most 404 pages are unvarnished geek-speak." Jeff lays out 5 ways to make the 404 error page better.
Drop the 404
Yes, the HTTP response code is 404, but there's absolutely no reason that ever needs to be shown on the actual page. Error codes aren't helpful. A simple explanation of the problem in plain English is all that's required. Any 404 page that has the characters "404" on it, if not already an outright failure, is already well on its way to becoming one.
Automatically notify you of the 404.
Repeat after me: it is not the user's job to inform you about problems with your website. If you require the user to click a button to notify you about a 404, or if you require the user to fill out a broken link form, you have utterly failed your users. 404 notification should be automatic, and by that I do not mean "sit in my log files until I eventually have time to look for it". I suggest weekly or monthly 404 rollup reports, emailed automatically to the powers that be. I'd also recommend real-time email notification if there is a sudden spate of 404s, so you have an opportunity to fix the problem while it's still relevant-- before the world gives up on your seemingly nonexistent page.
Try to find what the user was looking for and provide links to possible matches
Don't just put a search box on the 404 page and force the user to perform a search. That's a cop-out. Instead, automatically perform a search on their behalf, using the erroneous URL as the search input, and display those results on the 404 page. You can also try to correct the URL, based on rules derived from the top ten or top fifty observed 404 errors. Does the URL end in .htm instead of .html? Is it spelled wrong? Are your URLs case-sensitive? Was the page moved, renamed, or reorganized somewhere else? It's sensible to have a search box on your 404 page for convenience's sake, but forcing the user to perform a search should always be the method of last resort.
Present links to the most popular or most recent items
If someone is visiting your website, statistically speaking, there's a good chance they are coming to see the same attraction everyone else is. Even if they aren't, your popular content is popular for a reason. Why not present links to your "greatest hits" on the 404 page? Similarly, if you run a periodic website like a blog, or a newspaper, display the last few articles or entries on the 404 page. And at the very least, you'll want a link back to the main website. Provide a filtered list of relevant links, and an errant user will never be more than one click away from escaping their current predicament.
Keep the 404 page simple
Your 404 page should be brief, concise, and to the point.* You're already dealing with confused users who can't find what they're looking for. Don't add insult to injury by spamming the user with a giant, complicated 404 page containing a complete sitemap of your website. For example, the apple.com 404 page makes this mistake.
All very good tips which I've implemented to varying degrees on slashstar. When I upgrade to the latest Community Server, I'll try to integrate the inline search and intelligence because I agree that's a much better approach.