Solution: a .htaccess file at the root of the old domain to redirect old pages. Users as well as Google will automagically follow those redirects (with a 301 server response code to tell them that the page has moved permanently) and receive the new pages.
Creating that file requires a lot of manual matching and copying and pasting
Better solution: Use an app which will scan both versions of the site, compare the pages, make 'smart matches' and produce that .htaccess file for you.
404bypass uses the Integrity scanning engine to quickly scan your sites, compiling lists of your old and new pages. It can then use smart and manual matching to quickly and easily produce that redirect file.
The use of templates means that you can tweak the format of your output file, or export your matches as other types of file. csv is built-in, and you can even create your own templates, giving the app uses that we may not have thought of yet!
The manual is here
Download from here (First public beta is free for a limited time)
Screenshots below.