This might be a no-brainer but I can't decide whether the 404 error page should link back to the page, from which the user has come, or should it direct to the main page where the user can navigate to any part of the site? Making links to previous pages is really hard to implement since I will need to incorporate some sort of session cookie or something to track the previous URL.
Well I think I just found the answer to my own question but I'll be glad to listen to other inputs too ,I believe having a sitemap of the various links on the site would help or atleast a sitemap of the main pages on the site (if the site is too large to have a full fledged sitemap on the 404 page)
Heinz ketchup does this really well
Assume that a user is as likely to land on a 404 page from a search engine as they are from a page on your site (more likely, actually). That being the case, the most logical place to take them is the home page. (You might also take them to a search page, but only if you think that's a better experience.)