To use the photorec tool you need to install the testdisk package. I use the following command on my Debian system to install it.

apt-get install testdisk

Now you should make a directory (on another disk) on a partition that has as much space as the drive you are trying to recover. If photorec could somehow recover all of the files and the failed drive was full, you'd need an equal amount of space to store the recovered files. Better safe than sorry.

Now we want to run photorec and tell it which disk to recover and where to put the recovered files with the following command

photorec /d /share/recovered_files /dev/sda

photorec will now ask us a couple of questions, the first of which is what media to recover the files from (the default should be the disk we specified). The next question is what type of partition table you have. For most of us this will be Intel (unless your are running some other architecture). The next thing we will want to select is which partitions you want to recover files from. In this case photorec won't show us any partitions because we deleted the partition table, but we want to recover the "Whole Disk" anyway. Now photorec takes off finding our files.

When photorec is done, we should see a directory tree under the directory we specified which contains all of the files that were able to be recovered. The files will have the correct extensions, but otherwise they'll be named in some generic pattern.