rsync and take a snapshot, don't work from the snapshot, just keep it around in case you screw up a sed/rpl/awk rm, etc. During portions after verifying that your mass replace/delete/etc was successful, take another checkpoint snapshot so that you have a known good to go back to rather than working through everything once again.
things to look for '<iframe' '<script src'
You're likely to find some script src that refer to javascript loaded from the site, check the very end of each of the existing .js files
Check the .htaccess and make sure they look sane and haven't added the ability to run other extensions as cgi scripts or php files. Check your .htaccess for any php prepends, odd mod_rewrites.
Clean up obviously dead files, i.e. the .bak files, etc. Look in the image/uploads directories for any .php files, consider putting in mod_rewrites or remove mimetypes to make sure code can't be executed in directories that should be static content.
Dump your database, again search for iframe/script that is attached to fields that shouldn't have html, i.e. category names, etc.
get webmaster tools running, it will give you a little more information about what to look for.
Now that you've gotten the easy stuff out of the way, you need to look for ways that they did this. Since you've moved hosts, you've lost some of your forensic ability since file ownerships and permissions may have changed. Now you've got to look for scripts that contain potential badware.
(r57|c99|c100)shell passthru, exec, system, eval, popen, base64_decode, rot13
Hopefully remote includes are disabled, globals should be disabled, etc.
You're going to get a lot of false positives. Once you have that list, you can weed through and probably catch them quickly. If you believe there are remote shells and you're not really sure what they are running, consider installing suhosin, look for the line in execute.c around line 1588:
goto execute_internal_bailout;
and comment that out, run it in simulation mode,
suhosin.simulation = on
suhosin.executor.func.blacklist = include,include_once,require_once,passthru,eval,system,popen,exec,shell_exec,mail
Check your syslog for things that are reported.
When you look for code, you'll see things like:
eval($_COOKIE['blah']);
which allows them to execute commands, but, using a GET rather than POST so that you don't see the requests as easily in the logs. Since you're mentioning malware, it was installed somewhere, remote shells are probably the main reason, but, a lot of malware that is appended to a number of files is done through FTP. I would suggest that they change the FTP password. Definitely grep the logs for any POSTs just in case.
Not that you want to hear it, but, typically a webhost's backups are for disaster recovery, i.e. hard drive crash. If it hasn't been detected quick enough, their nightly or weekly backup could get overwritten before it is noticed.
Most of the exploits I see modify php files and add some code at the bottom through FTP, or, do a global search and replace with a remotely executed script.