Redirection: should I redirect, and if so, where?
In general, no.
Not unless you're pretty confident that you know where the user actually wanted to go (and in most cases, you won’t). It’s better to give them the explicit error message, and let them decide where to go next.
If the user is trying to reach an old URL which has been moved, it's fine to redirect them to the old URL. But you should really be using a 3xx redirect instead of a 404.
Should the page explicitly state 404: Page not found?
I like having the 404 on the page, because I think many people know what that number means, and it acts as a shorthand for the error. But that's just a preference – for example, Apple and Microsoft's 404 pages don't mention it.
There should definitely be phrasing to the effect “the page was not found”. That's a common and well-understood message.
How should the page designed?
It should fit in with the rest of your site. You don't want to confuse people into thinking they've accidentally gone to a different site, rather than finding a missing page on the site they were actually looking at.
Who should be blamed?
Nobody. The simple message “The page was not found” is neutral and accurate.
- Putting blame on the user will annoy them; putting blame on yourself is unnecessarily self-deprecating.
- You can't tell whose fault it is. Perhaps the user typed in a nonsense URL (their fault), or part of the site is broken (your fault).
It's not appropriate to point the finger of blame; it would be easy to get it wrong.
Any other suggestions?
The URL the user types in can give you information about where they wanted to go. If you're careful, you can use this to redirect or suggest an alternative. (This assumes you don't have lots of similar URLs, and that you have some sort of finite list to compare to; this won't work on all sites.)
I like the Apache mod_speling module. If the page isn't found, it looks for pages that are very similar (a one or two character difference), and redirects appropriately. It's a good way to catch typos. But it's pretty conservative, because redirecting to the wrong page is probably worse than returning an error.
When it's too far off a genuine URL, you can still suggest what the user might have typed. This is an idea from Brett Terpstra: his 404 page suggests similar URLs to the current page. For example, this is the result for http://brettterpstra.com/2013
:

Those aren't appropriate for all sites, but I think they're interesting ideas, and potentially a bit more useful than a generic error page.
404 Error not found
would indicate the error itself isn't found.404 Page not found
is more common.404
error page had the404
on it along with some random messages like "Sorry, the page you were looking for was eaten by the dog" or "A hamster used this page as his bed". It adds a nice customization to your site depending on what is it about, but also has to be noted that it quite depends on the user knowning what the404
actually means.