ErrorDocument 404 /error.php
in your htaccess (if your host supports this)
Then make error.php which should be a 'smart' 404 page which checks what page was requested. If it's an old url that has moved, it 301 (permanently) redirects to the new location. If the page genuinely doesn't exist, it should give a 404 error as usual.
The 301s should help pass along pagerank etc to the new pages, and also help search engines get the new urls in the index quickly. Most search engines don't really like meta refreshes and other javascripty redirects too much.