Create a new node (node/add/page), and ensure you can enter PHP code in your page body (check input filters).
Insert the following code into the body of your new page:
<p>I'm sorry the page you are looking for cannot be found.</p>
<div id="error-search-box">
<?php
// check that the search module exists and the user has permission to hit the form
if (module_exists('search') && user_access('search content')) {
$path = $_REQUEST['destination'];
$keys = strtolower(preg_replace('/[^a-zA-Z0-9-]+/', ' ', $path));
print drupal_get_form('search_form', NULL, $keys, 'node', 'Search this site');
}
?>
</div>
Save this new page (ideally with a custom URL of your choice: such as /page-not-found) and tweak your CSS accordingly.
So that Drupal will send users there when HTTP 404 errors are generated, go to admin > settings > error reporting (/admin/settings/error-reporting), and set the default 404 error page to page-not-found (or whatever). (You might want to do a 403 error page while you're here too).
If the above phases you out, as with all problems Drupal, there's a module for that... the thrifty404 module will do exactly the above, but you'll need to do a bit of cunningness in the Drupal theming layer to customize it.
And Bob's your aunty's live-in lover..!
