Google implemented a similar error page for google.com and now you can add it to your own site. If you have access to the web server and you can customize the 404 error page, Google provides a widget that enhances the page. "The 404 widget is a quick and easy way to embed a search box on your custom 404 page and provide users with useful information designed to help them find the information they need. Where we can, we'll also suggest other ways for the user to find the information they need, thus increasing the likelihood that they'll continue to explore your site," explains Google.
The widget can be found in Google Webmaster Central, by selecting a site from the dashboard and clicking on Tools > Enhance 404 pages. Unfortunately, it requires JavaScript, so a small number of visitors will not see it.
Google has some recommendations for creating useful error pages: informing visitors that the page could not be found, recommending popular pages from the site, using a consistent design and preventing 404 pages from being indexed by search engines.
The Webmaster Central Blog mentions that this feature is experimental and that not all the sites show great suggestions.