404 pages are error pages, and how you deal with errors (like dealing with complaints) says a lot about your business.

To some extent 404 pages are inevitable, so look at them as an opportunity to impress your users - you should approach the design for your 404 page with that in mind. Ask yourself; if you were a user, what would you like to see on an error page?

Lets take Apple's 404 page as a good example: http://www.apple.com/404. This is a good example for a number of reasons that I will list now.

1. The menu bar at the top of the page is the same at the rest of the site. This makes it clear that you have not accidentally left the site, secondly it means that users who are familiar with the site can find the section they were looking for quickly and easily.
2. The statement "The page you’re looking for can’t be found." is clear, friendly and unambiguous.
3. The search box is clearly available for the user to attempt to locate what they were looking for.
4. The full sitemap link makes it very easy to move on, or to locate other resources.
5. Lower on the page the standard and comprehensive footer again provides a variety of direct links to help the user navigate away from the error page.

So Apple have all the bases covered when it comes to a perfect 404 page. Lets take a look at the reasons...

1. A continuation of on page design elements that make it clear you have not left the site by mistake.
2. The page clearly states that there has been an error - "This page can not be found".
3. Quick and easy methods - either direct links or a search - so that the user can get back to where he or she expected to be.
4. One other point to note is that the actual HTTP status code "404" is not shown anywhere. The specific code may not be of any interest to a user and could cause confusion should the user not understand what this code means, it's important to decide whether this information is useful to your target audience.

There is some good information about creating and handling 404 errors from Google here.