The details of how this occurs depend on the operating system (OS) the computer is running, but the basics tend to be similar. A computer disk stores information in a series of chunks known as sectors, each typically 512 bytes long. Each sector has a number that serves as its address on the disk. A file on the disk is split across a number of sectors. These sectors may be located together but might be scattered across the disk if there is not enough contiguous space in one spot. The OS has an index mechanism to keep track of which sectors belong to which file--the particular mechanism varies by OS, but they all do it. Additionally, because sectors are addressed by numbers and people care more about names than numbers, the OS also stores a directory that maps the file name to the index entry about which sectors contain the file's information.
As an analogy, consider the disk to be a filing cabinet that contains a long series of consecutively numbered folders, each of which can contain only a few pages of information. A particular document might be split among many folders if it is too big to fit in just one. The first drawer of the cabinet holds a big directory that has a list of all the documents in the cabinet. The folder number associated with a particular document holds an index to all the other folders that contain the parts of the document.
When a file is deleted, the information stored in the individual sectors is not erased, because the erasure process consists of overwriting the sector and is relatively slow. It is significantly faster to overwrite the sector by rewriting it with new data only when it is needed for some other file. So when a user "deletes" a file, the directory entry for the file is either removed or marked as deleted by changing the first letter of the file name to a special character (which again differs depending on the OS). The index entry and the sectors are then made available as space for new files but are left untouched until needed.
A deleted file can thus be recovered if the index information and sectors have not yet been reused. The chances of this are better if little computer activity has occurred since the file was deleted, so it is best to attempt to recover the file as soon as possible. In operating systems that simply change the directory entries, recovery programs have a pretty easy time. They scan the directory for filenames that have the special character that signifies "deletion" and present a menu of files to recover. When the accidentally deleted file is chosen, the directory entry is corrected and the file reappears. In other operating systems, the recovery programs have a more complicated task. The name that was in the directory may be lost, making it harder for the user to find the specific file she wants, and the program generally must look through all the index information and attempt to recover files from their individual sectors. Also, because sectors may have been reused from the middle of the file, only parts of the file may be recoverable.
Answer originally published December 15, 2003.