In the content div, put something like "404 Page Not Found" between the <h1> tags and remove everything else between those tags.
In the post-bodycopy div, put your custom message (you'll need to use <p> tags) and remove everything else. Links to your home page, search page, site map, last post, and/or whatever you want can be included.
Save the template. To test it, simply enter a nonexistent page url of your site into your address bar.
Here's the official WP codex doc.
As an example, here's what I put up for now:
Code:
<h1>404 Page Not Found</h1> <div class="post-bodycopy cf"> <p>Oops!</p> <p>The page you requested wasn't found.</p> </div>
It's possible I could have stripped out more code from the template to make it more elegant, but I didn't dig into what that would do.