One approach is to choose a new URL naming scheme that will allow you to set up the 301 redirects with a few lines of regex in your .htaccess file. In other words, use a modification of the old URL scheme in some easily coded form.
I redirected 80 000 URLs to a new structure on a site last year. Traffic dipped for a short while then increased.
How you redirect depends on what the old URLs look like. You'll probably be better off rewriting requests to a PHP script that then looks up the new URL in a database table and then issues the redirect. It is important that the PHP script returns a 404 header for non-valid requests that manage to invoke the PHP script.
There's one more option. KEEP all the old URLs, and simply rewrite-- not redirect-- to the new location. This is a good option if the old URLs are prettier than the new URLs, and the new CMS doesn't have a horribly complicated set of rewrites that you'd have to work around.