Tyler Faile's analogy is great.
The data doesn't go anywhere. The address of it is simply marked as free space, and is then overwritten when new data needs a place to go. As soon as it's overwritten then it is gone permanently.
If you want to delete something so that it won't be recoverable you can either directly overwrite it, or overwrite all the free space on your hard drive. You must be careful about simply overwriting files though, as files are moved around by the OS during normal use. If this happens the old copy won't be securely overwritten.
A good program for overwriting files, and overwriting all free space is Eraser.
A good program for overwriting entire hard drives (perhaps before selling them) is Darik's Boot and Nuke. Be very careful with this program. Its name is quite accurate. Don't use it unless you are certain you don't want any data on a computer.
There are often debates about if data can still be recovered after a single overwrite. The fact is this has never been publicly done on a modern disk. Peter Gutmann wrote a paper about this, and one of the methods is named for him. You can read his paper here:
This is what he has to say about multiple pass overkill:
In the time since this paper was
published, some people have treated
the 35-pass overwrite technique
described in it more as a kind of
voodoo incantation to banish evil
spirits than the result of a technical
analysis of drive encoding techniques.
As a result, they advocate applying
the voodoo to PRML and EPRML drives
even though it will have no more
effect than a simple scrubbing with
random data. In fact performing the
full 35-pass overwrite is pointless
for any drive since it targets a blend
of scenarios involving all types of
(normally-used) encoding technology,
which covers everything back to
30+-year-old MFM methods (if you don't
understand that statement, re-read the
paper). If you're using a drive which
uses encoding technology X, you only
need to perform the passes specific to
X, and you never need to perform all
35 passes. For any modern PRML/EPRML
drive, a few passes of random
scrubbing is the best you can do. As
the paper says, "A good scrubbing with
random data will do about as well as
can be expected". This was true in
1996, and is still true now.