To what extent does formatting a disk (securely) remove its data?

Quick-formatting a hard disk simply erases the filesystem's structures and tables and writes new ones in place, giving the illusion of a brand new disk. Old data is simply overwritten as and when needed, but it still remains on the disk. File carving utilities can go through the disk data and recover fragments of files, then stitch them back together without needing the original filesystem entries. This is commonly offered in commercial "undelete" applications, but more comprehensive methods are available in forensics packages.

Wiping a disk with a single pass of random data (or zeroes, or whatever really) is sufficient to fully remove all traces of the data from the overwritten sectors. Multiple passes are pointless on modern disks, even against the perceived threat of hardware-level recovery attacks. I refer you to this question for details, but the short answer is that old techniques like magnetic force microscopy (MFM) were never really effective at recovering overwritten data in the first place on low-density devices, and newer magnetic disks have such high densities that it's physically impossible. Multi-pass overwrites are there to help people validate their need for über-security, or sell magic disk wiping software, despite it being pointless and detrimental to disk longevity.

The only exception is flash (e.g. USB flash drives and SSD), which have additional wear-leveling sectors to increase the lifespan of the device. The physical sectors are exposed as a logical map to the system, which makes it impossible to directly overwrite all of the data. Even if you overwrite all the logical sectors, old data might remain in the wear-leveling sectors. In order to combat this, some flash device specifications include an encryption requirement to increase the difficulty of recovery (because it is no longer possible to directly read data from the memory chips using hardware probes).

In SSDs, encryption can be used to speed up the ATA Secure Erase feature. All sectors on the disk are encrypted using a key stored in hardware, and this key can be discarded and a new one generated when a Secure Erase command is sent to the device, thus rendering all data on the disk (including slack / wear-leveling areas) unreadable. Secure Erase is also possible without encryption, but then the drive must actually delete all memory cells, which may take a while.

One part of your question seems not to have a good answer, so I want to add to this:

By formatting a drive, you typically choose to do a "quick format". This does not overwrite the data, but only clears the information where each file is stored. Therefore, it is as easy as starting a program to recover a hard drive that has just been "quick formated".

Maybe this comparison helps you to understand this better: Your hard drive is like a book - and the partition(s) and the file system(s) are the table of contents. A quick format only erases the ToC. This is faster than erasing each single page - but the information in the book stays recoverable.

At least for classical hard drives, overwriting each single sector should provide enough security for most cases.