How to create a Joomla 1.5 Custom 404 Error Page
Joomla! CMS uses the templates/system/error.php file to handle several HTTP Status errors, including “403 Forbidden”, “404 Not Found”, and “500 Internal Server” Errors. You may style the error results by directly changing the templates/system/error.php.
But it is not advisable to hack core system files as those changes can be lost in an event of a Joomla update process!.
So best way is to use the template overriding and add a error.php file to your default template and customize it.