If you can catch them, and you can find a matching new result, I suggest you header like this (in php, maybe you want something else):
header("HTTP/1.1 301 Moved Permanently");
That way, if you have
/some/TESTPAGE with some PR value, and you link it to
/new/TESTPAGE via a 301, you move the PR value with it, instead of loosing it.
If you can't find the new page, and they get on your site, send a 404:
header("HTTP/1.0 404 Not Found");
// You can add a default "not found page", or simply exit.
This will not preserve PR value. You kinda allready should have the 404 method though, this is good for SEO (all the not found pages will be duplicate content otherwise).