A normal format simply deletes the contents of the disk records. To securely delete the data a program such as that recommended must be used. In the case of a traditional hard drive all the data must be written over several times as a single pass will not usually securely delete the actual track completely.
"I thought formatting always over wrote data with gibberish that could only be cracked by police and security services."
That's not the case - formatting a drive removes the address tables, so you can't see the files, but the file data are not erased, or written over with gibberish. Anyone with the necessary software can recover the contents.