I would like to understand what does formatting really remove.
When a computer "formats" a disk, or a partition, that means creating a filesystem volume. A "volume" is basically a place where files are stored; for old floppy disks, the entire disk was basically the volume. For hard drives, a volume was stored in a partition, and one disk could have multiple partitions (meaning that it would have multiple volumes).
Basically, formatting ends up creating a blank table. When I say "table", you can think of a chart with rows and columns. Each row refers to a filename. Each column identifies a file fragment. For instance, "the first fragment of this file is at sector 1000". "The second fragment of this file is at sector 2000". The formatting process creates a blank table, and then that table gets filled in as files are created. With DOS, the filesystem type was named after this table, which was called the "File Allocation Table".
If you're not worried about old data, and who might access old data (which might be a concern if that data is confidential/sensitive), then your best bet is to do a "quick format", which just creates the minimum details for the filesystem volume that keeps track of files. If you have a choice between a "minimal"/"quick" format and a "full"/"extended" format, then the latter format is likely to do something to each disk sector that is part of the filesystem volume. That may mean erasing each sector, or just trying to do some other check to make sure the sector is physically usable.
When launching a computer, something shows up, resembling DOS.
Like LPChip's answer, I'm presuming that you mean the "system startup" process. On older machines, this was commonly called the Basic Input/Output System, abbreviated as BIOS. There are certain standards about how a BIOS worked, so that computer software (like the operating system) could interact with parts of the computer. Many newer systems use a newer standard, called (U)EFI ((Unified) Extensible Firmware Interface). I haven't found any term that the industry has widely used to describe both the BIOS and the (U)EFI standards, so I just made up the term "system startup".
The primary reason I would think you might be calling this as "resembling DOS" is the use of text mode. (Good ol' CP437!) However, from what I've read, I've had some impression that (U)EFI can be controlled with a command line (maybe with just some implementations).
This can't possibly be stored on a hard drive ? Where is it stored then ?
This is typically stored entirely in some chips. On older systems, these were ROM (read-only memory). However, when new technology (like bigger hard drives) became incompatible with the chips, people had to physically replace the chips to support the newer technology. In the late 1990s, people started using writable memory, which they often called "flash memory". Such memory is not intended to be written to very frequently.
When you change configuration options in that system startup softare, your configuration's details get stored into some other memory, commonly called CMOS. That is a small bit of memory (different from your RAM), stored on the motherboard.
I read that there is a boot sector on the hard drive, is there some leftover on the hard drive after formatting it ?
Systems using the BIOS standard would check hard drives to see if the 511th and 512th bytes contained these bits: 0101 0101 1010 1010
If so, the disk was considered "bootable", and the BIOS would tell the CPU to start following the instructions located on the first byte of the disk. The first 512 bytes of the disk were called the "Master Boot Record" ("MBR"). Code stored in the MBR had to be rather small, because the 511th byte had to be 01010101 if the computer was going to boot. Actually, what most of this bootable code would do is to check the 447th through 510th bytes using a standard called the "partition table". Bytes in that table would specify where there was a partition (or more than one partition). Commonly, the first partition would start on the second Cylinder of the hard drive. (With old hard drives, the term "cylinder" referred to a physical characteristic of the hard drive. That meaning was a bit lost when Logical Block Addressing often made the numbers correspond less to the disk's physical design.) The main job of the code in the MBR would be to check the partition table to see where the filesystem volume started, and then start running code from that location.
(U)EFI is a bit more complicated, understanding the more complicated GPT structure.
In any case, formatting has nothing to do with this. Formatting is related to data within the partition (often starting on the second cylinder, which was often called Cylinder number 1, because the first Cylinder was often called Cylinder number zero). So formatting should not affect the initial boot code that the MBR uses on the disk. However, formatting may affect the code that the computer tries to use after the MBR's data is used.
Does it really ends up with 0 bytes left on a drive ?
You mean 0 bytes used up? Absolutely not. There are absolutely bytes used up on the drive. The partition stores the filesystem volume, which contains the table that will be used to keep track of filenames and where the file's fragments get stored. Commonly there are other details, such as a "label" (which is a name you can assign to the filesystem volume). This ought to be a relatively small amount of the disk's total data, but this is a part of the disk that gets used up.
When you ask your operating system how many bytes are available, the operating systems typically report how many bytes can be used to store files. That is the data that most people are interested in. The operating system is not reporting the bytes that are used to store the file table, nor bytes outside of the partition (like the MBR).
However, since the table is empty, all bytes that can store file fragments are available, and zero of those are used up. The contents of old files might be on the disk, if the disk was quick-formatted. (A program like TestDisk may be able to help find such contents.) However, when you ask the operating system to store new content in new files, the operating system will use those areas of the disk (because the table doesn't say that those areas of the disk are storing any file fragments that we care about). So, the old data can get overwritten by new data (which will cause TestDisk to be able to recover that old data when it happens). Note that even if the contents of the files are saved, details like the names of those files might have been overwritten when the disk was formatted. (I say "might" because there are different ways to store files. Some of those ways of tracking data might involve a table that has a consistent size, using up space to keep track of sections on the disk even when those sections aren't storing files yet. Other methods might vary the table's size depending on what data is stored on the disk, so an empty disk may have a small table. So maybe some of those filenames are still physically stored on the disk, but the operating system isn't keeping track of that old data, and so that data is also likely to be deleted when the operating system finds a benefit to doing so.)