This is actually very easy and can be done by anybody hosted on a standard server.
A custom 404 page can be very helpful, it can save people leaving your site and it also adds a nice personal touch to your site.
My site's here...
Step 1: Build a Page
Make yourself the 404 page you want - I decided to go a bit silly with mine, it's actually just one big image, with an image map overlaid, because that's the way I fancied doing it just then.
Save your custom 404 page in the root of your site.
Call it something like "my404" or "errornotfound"
Step 2: Make the Special File
Open up notepad or some such.
Now type or paste in.
ErrorDocument 404 /errornotfound.html
Or if it was called "my404"
ErrorDocument 404 /my404.html
You need to save this file as .htaccess if it's notepad, use quotes when saving otherwise it'll get saved as .htaccess.txt which is no good.
Alternatively save it and edit the extension in the file name, if you've got view file extensions checked off in your options.
Step 3: Send the Files
FTP these files to your website server, wait for it to refresh then try typing in a random page that doesn't exist.
Basically the htaccess file instructs the server to show the file you specify in the document when a 404 error is served up.