It would be an .htaccess file, and it would have to be in the old domain's root folder (the subdomain where you were hosting WP before.) Do you still have access to that domain? Here's the syntax:
Redirect 301 / http://domain2.com/
Redirect 301 /2006/ http://domain2.com/2006/
Redirect 301 /2006/07/ http://domain2.com/2006/07/
etcetera. You don't have to use an absolute URL for the old file location, but you do have to use an absolute URL for the new file location, regardless if it's still in the same root. I changed the permalink structure on my blog a couple months ago and had to do this for every single page on the site. Needless to say, it gets big quickly.