You could use mod_rewrite with some regex like this:
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteRule ^/old/(.*)/?$ http://newdomain.com/new/$1 [R=302,L,NC]
</IfModule>
This would go in the .htaccess file in the olddomain.com document root.
I’d suggest leaving it as a 302 until you are sure it’s having the desired effect, as most browsers will cache 301’s and then not look at your .htaccess anymore just follow the cached routes – which can be tricky to clear (you definitely don’t want to be explaining how to clear them to end users!).
Also, this isn’t really a WP question.