You may be interested to know that when a file is deleted (and the recycle/trash bin is emptied) the actual data is still sitting on your disk. This applies to magnetic storage such as Floppy disks, and the common hard disk and even flash storage devices such as Memory Sticks, Compact Flash, Micro Drives and similar technologies.
When a file is "deleted" what actually happens? Your operating system removes the reference to that file on the file system. This reference had details such as where on the disk the file was. Whilst marked and available as free space the old data didn't move, its just not seen on the file system but physically exisits on the disk. The entire file remains on the disk until another data is created over the physical area, and even then it may be possible to recover data by studying the magnetic fields on the platter surface.
Recovering deleted files
Since when a file is removed the data remains then it's perfectly logical that software utilities exist to un-delete this data back to life. (How else do law enforcers do it?).
Recovery tools do not read the actual file system. They read the contents of the actual disk, thus it can list the "deleted" files and offer an undelete option.
Files are stored in clusters on the disk. Say/assume each cluster was 8192b in size and you wanted to recover a 14KB file. First the file is stored on two clusters (note, that a file is stored on 1 cluster or more. One cluster cannot hold two files). The recovery tool will simply extract the data in the clusters and actually save it, thus the operating system can see it again.
Now you can understand why deleting a personal file, or clearing your Internet Cache doesn't mean it's gone for ever. This document doesn't go deep into data recovery. The aim is to make the data non-recoverable.
Securely Deleting Files
There are several software tools that will "securely" delete your files. Let's examine them to see how they work. Rather than deleting your file normally you use a secure deletion tool to do the job. What it actually does is it removes the reference to the file (as Windows does). Then the tool inspects the clusters on which the data exists and overwrites them with random data which is determined by complex mathematic algorithms. One "pass" means overwriting the clusters once and will render most commercial recovery tools useless. However even one pass is considered weak as agencies such as the FBI or CIA (who have the money) can probably recover most of the data. 7 passes is what's considered as "military" grade. As the number of passes increase the chance of actually recovering the file with today's technology decreases close to an exponential rate. Most tools allow you to delete files and can also "wipe" free space - that is overwriting clusters that were marked as free space. The more passes you select the longer it takes for the task to complete. Also note that most of the on the shelf tools require strict rules to operate. Basically the data you want to recover has to be "perfectly" there on the disk (even though it's not referenced). Take that 14KB deleted file mentioned earlier and remember how we assumed it was stored on two clusters. Say that you saved another file, and it was saved on one of those clusters. Suddenly for most on the shelf tools that file can no longer be recovered although law enforcement agencies can still recover parts of the file and inspect it for vital evidence.
Your best chance of recovering a file is when it hasn't been deleted via a secure deletion tool and when you use a recover tool just after the file was deleted normally. The longer you wait the higher the chance that the operating system has placed a new file over the area you want recovered.
Formatting the hard disk simply re-creates the file system, again the old data remains on the disk (but the OS can't see it). Some recover tools can dig into "old" deleted partitions and recover the files that use to be in them.
Peter Gutmann has written an excellent paper titled "Secure Deletion of Data from Magnetic and Solid-State Memory" this provides an excellent insight and more technical details on the topic