Seconding TestDisk/PhotoRec. Used that when my laptop went all "Fuck you" and mangled some files I desperately needed. Has versions for Linux, Windows and Mac, and it's all free. Someone in the forum where I originally got the link commented something to the effect of it recovering any file that has so much as breathed on your HDD, and holy shit they were not kidding. I found things in the recovery folders that I had deleted two years ago. So yeah, Chim is a big fan of this particular bit of software.
One thing to note if you still want to recover anything from a disk is to stop using that disk. If it's the OS drive, the OS will continue to write to that disk that may make it harder to recover your files. I never lost any files on my Mac (I just leave them in the trash can), but I have lost and recovered plenty of files on Windows. The only application that I could find that is freeware for Mac is TestDisk/PhotoRec.
There are two methods recovery software uses to find "lost" files. The one that takes the short time (about an hour) can usually recover files that were recently emptied from the Recycle Bin by scanning the Master File Table (it's like a table of contents, but for your hard drive). The longer one (can take hours/days to complete) scans the data blocks themselves and can completely or partially recover old files. This is for NTFS, so the wording may be a little different for HFS+.