What you do
not want for "page not found" is the server's default 404 page.
You need to do two things: build a custom 404 page, and make sure that that page is what your visitors (and searchbots) will get if the page they're seeking isn't there.
Taking last first: you put a simple line in your .htaccess file (I presume you are using Apache and so have one, and that you know what it is and where--typically in your site's root directory).
You insert in that .htaccess file a line approximately like--
ErrorDocument 404 /myown404.shtml
I say "approximately like" because you can make its name what you want (but you need to, as that line is written, have it in your root directory). You can use, as suits your needs, an html page, an shtml page (useful if you have an "includeable" site directory), or even--and perhaps most inventive and useful--a php script.
Which last brings us to first: what the page is and does.
Naturally, you want it to look pretty and to be genteel in delivering its message, sort of "Er, um, sorry, we don't seem to have that one in stock today". But besides being genteel in explaining that there's no such page, you should do more. At the very least, direct your visitor to your site's home page. Better, if practicable, include directly or by link a Site Directory. But if you're clever and know some php, you can do ever so much more--how much is up to you. Some webmasters have the page send them an email with all the data (including the request, the visitor's info, and whatever else you like); others auto-log it somewhere.
You also
may be able to use php's parsing abilities and some ingenuity to detect what page the visitor
probably wanted, and redirect him or her there--that depends on your site setup and your exact pages. (If, for example, you re-ordered your directories but not your file names, it's cake.)
Note: if you use php scripts much on your site, it also behooves you to have your own 500 page, for when a script is not found.