Some possible stages of erasing data:
Deleting file in Windows: the link to the file is reverted to the trash bin.
Removing a file in Windows: the link of the file in the trashbin is removed.
Quickformat: removes (resets) only the file allocation table of the OS.
With all the above, the data of the file(s) still physicial exist and can be recovered easly.
(Normal/Full) Format: resets the file allocation table, root directory, etc of the OS to their original. Also the sectors (once occupied by file(s)) are reset (aka: put to 0). This means the HDD can still directly be used in Windows as every special sectors will be recreated.
These are also know as high-level formatting. It means that the formatting is performed by the operating system's format program (eg: the DOS FORMAT program or Windows format program).
Destructive Format (not possible in standard Windows): It sometimes means the same as a normal/full format. Or it is the same as normal/full format but it is done several times (see below about the 3-pass format type).
Low-level Format (not possible in standard Windows): removes (resets) all important parts of the HDD as well as all the sectors. This includes partitions, boot sectors, FATs, etc... In short: every possible bit on a physical level. When doing this your harddisk must first be partitionated again and proper boot sectors, FATs, etc must be created if you wanna reuse the HDD (this can be done with the DOS command FDISK for example)
This is (almost) as far as you can go with normal available programs. But this is also were it gets interesting. Fully low level formatting a HDD will overwrite everything with zero's. You would think everything is gone. *BUUUUUUUUUP* wrong!...
HDD have one flaw: the way they work
, aka magnetism. For a HDD you like to think that it holds digital information, a bunchs of 1's and 0's. This is true, but that digital information is stored in an anolog form (aka: non-digital). Two parts of the physicall anolog data (the two digital bits) may both actually be reconized as 1 for example, but in reality one of them may not carry as strong a mangnetic force, a strong indication that the previous value would have been a 0 instead of a 1. This is because overwritting the same spot on a HDD with a 1 emphasises/builds up the magnetism of that part. So, in other words, such bits retain a history of what was previously there. So if you would overwrite all bits on the HDD with 0's (like you would with a full format), the physical parts on the HDD will still have different values of magnetism (although less enough to not be detected as 1's in normal computer software).
With specialized professional equipment (this is what the police have and use when they talk about recovering data for crime investigations for example) it is possible to "read" these very small differences in magnetism and thus reconstruct the true digital bit (0 or 1) of what has been there.
To overcome this kind differences, you'll sometimes see, in specialized formatting programs (you can google them) a method where each byte on your HDD is overwritten 3 times with a certain byte value (or with a random one) before the basic one time overwritting with value 0. This to ensure that the magnetism is as random as possible or as inconsistant as possible so the history can't be rebuild so easly. (The times for overwriting with another byte and the byte value itself can often be set in those programs). This is sometimes called a 3-pass format and can be used in addition to any type of format. Eg: a 3-pass quick format will overwrite the FAT 3 times with a certain value or random value before overwritting it with 0.
But, still... Yoda will say: still not gone completely the data is,... There are also other kinds of left-over magnetism. Edge-magnetism. Since the physical anolog parts on HDDs have been made slithly physically bigger then they should be (to overcome errors where the magnetism of one bit influences the one next to it), the chance exist that the original magnetism of a bit has been leaked to those (non-writeable) edges. Then there is another kind of edge-magnetism where two adjacent (writeable) parts could still influence eachother. So again, accessing those edges and reading the edge-magnetism can reveal the original data...
Though, it must been said, recovering data in such ways is only something very specialized companies or goverment instancies can do with very specialized equipment. Thus this isn't done with "normal" software and a computer as we know it. It is also not always 100% accurate of course, but it is possible in some extent...
----
So, to summerize, to make sure nothing can be recovered by normal means (aka: with "commercially" available programs), do a 3(or more) pass low level format. Programs which can do such stuff can be googled...
/ 
