Дьявол said:
You should do low-level format, and the deleted files will never be recoverable... :-)
You cannot do a low level format on most modern drives.
A low level format (back in the days of FM and MFM) wrote actual track markers onto the disk that were used as a guide by the head positioning - the same thing is still done on floppies but not on modern RLL drives. The head servo is accurate enough without them and the firmware can use the actual data tracks as references if needed.
An operating system level format will either just erase the file table (windows quick format) or also check the drives for bad blocks (windows full format). A Unix mkfs is similair.
NTFS also writes spare copies of the file table at the middle and end of the drive - just in case.
Even if the file tables are erased it is relatively easy to extract data from the disk - especially if you know the content of the file you are looking for, you just read each block in turn and check for the data. That's why to securely erase a drive you write zeros over every block.
However - if you are '3 letter agency' you can then take the drive apart and put each platter under an electron microscope and see the analogue pattern of magnetic data. If a point on the drive originally held a one and you wrote a zero then the magnetic field might only have been reduced to 0.1 - low enough for the drive to read it as zero, but enough to give the microscope an idea of the original content. This is where the recomendation to write over it with random numbers or some special pattern a certain number of times came from.
How much this matters for a modern high density drive (ie how close to 0 is the remaining field) is the point that is being debated.
Like anything else in security - it depends on how valuable the data is, and how much time/money/effort the other guy is prepared to go to in order to get it.
If you just don't want your friend to get your 'artistic' picture collection then a format and installing windows over the top is enough, if you had people's credit card details or medical records then use sdelete (write over it with zero) and if you had nuclear launch codes - smash the disk and dissolve it with acid!