I'm just wondering if someone with experience in Wordpress would share their knowledge on how to optimize the page, the best plugin for it, etc. Thanks in advanced.
Instead of a plugin, go with a page template. It should include a printout to the user of their typed in address. You can get this with PHP's $_SERVER["REQUEST_URI"] variable. You should also provide a search box easily accessible there. Depending on the likely knowledge level of your visitors, you may want to include a few steps they can try to fix the issue (Check your link for typos, try refreshing, etc.) Also, you could include a simple way for them to report the 404 if they believe it's in error. For example, they click on a link on your site and arrive there. (Of course, you should be aware of internal 404s already.) You should also have analytics tracking it as an event, saving the Request URI as a label, so you can see a listing of all 404s at your site. This is good for identifying common typos and external links that are incorrect. You can create 301 redirects for these. An amusing image is always nice for user experience too. They won't enjoy seeing a 404 page, but you can make it less not enjoyable by making it fun. (See Twitter's Fail Whale or Reddit's dead alien.)
I will be posting a video tutorial on this soon enough...but for now, I agree that a good 404 page is entertaining (funny pic) but should also let the user know that the page they are looking for IS somewhere. Prompting them to re-type the address, or going to your homepage is a good idea. A good 404 page makes the user want to keep looking at your site.