Let's say you deleted some files on a drive without meaning to, or you formatted and lost some data, or your hard drive just stopped working for some reason. It's often possible to get back what you lost, but you'll need the right software, meaning a copy of a file recovery OS on a CD or other bootable device (I recommend RIPLinux, which this tutorial is most specific to, but several others have these tools as well; I prefer RIPLinux because it's so lightweight.) However, make sure that the OS you're using doesn't mount all the partitions on your drives by default; this would be bad.
You'll also need somewhere to save the files you have recovered. This could be a second hard drive, USB stick (often too small) or the like. If you've just deleted files from one partition and are sure everything else on another partition on the same disk is safe, that might work, but it's not recommended.
Remember: The number one thing you don't want to do when working with a damaged filesystem is write to disk. Just starting up the operating system on a disk writes a lot of log files, and any of those could overwrite the data you're trying to recover. Don't mount the drive, either - you don't need to with the programs we'll be using, and just mounting the drive can cause it to be written to. Your data is fragile!
Burn a RIPLinux CD if you have to, pop it in your drive, and start up. You'll be greeted with a splash screen. The default option works if you know exactly what you're doing, but it's easier to boot to X because it gives you menus and some graphics. Select the “Boot Linux to X! (32-Bit Kernel)” option. After it finishes loading, you'll be put on a very bare X desktop with a menu bar that pops up at the bottom. Right-click for a menu. This is how we get to the various tools available on this disc. Both Testdisk and Photorec (which we'll be using) are in the Applications -> Partition Tools menu.
It is safer to work on a backup of a disk rather than the disk itself. However, doing this requires enough disk space to save a copy of it - and you'll need additional space to save recovered files as well. Use ddrescue (also in the “Partition Tools” section of the menu) to copy a drive. This is especially useful if your drive is having issues reading and writing properly; ddrescue is designed to get as much data out of a damaged drive as possible.
Read on for the specifics on getting your files back.