If I remember correctly, deleting a file in windows normally involves deletion of the index information for where the data is located on the storage drive. Essentially, because the location of where that data was stored is lost, and now the drive doesn't know what's there, the space is marked as "open" for use, or in more layman's terms, it becomes empty. This is why deleted files can be recovered in windows systems. The data isn't actually erased, its location has just been forgotten. Special programs and know-how can allow you to find that information again and bring it back.
There are two types of formatting, at least under windows. There is the quick format, which just deletes the entire drive index information. Again, all of the data is still there, it's just seen as empty to the OS and can be rewritten at will. Normally a quick format is all you need to "erase" a hard drive and make it empty. This is how you reformat and reinstall Windows when you use the Windows install utility.
Then there is the full format. The full format actually truly erases everything on the drive by writing every bit in a 0. This information is generally unrecoverable. Full formatting takes a long time (upwards of an hour and more depending on the size of the drive) on hard drives, versus a quick format which only takes a few moments to perform.
Someone correct me on anything I may have gotten wrong.