How does pre-boot authentication with disk encryption work technically?
If the whole disk is encrypted, and some pre-boot tool asks the user for a key to decrypt it, doesn't that mean this tool has to run beneath the OS that's going to boot?
Yes, pretty much. Hardware-based full disk encryption does this: the encryption is handled entirely by the device (hard disk/flash) or possibly in a controller along the chain leading to the physical device(s), and is not "visible" to the OS.
With this, the OS does I/O exactly like it would if it was dealing with a plain, unencrypted device, the magic happens in hardware (and/or firmware - "below" the OS in any case).
If there's no such tool, doesn't that mean the decryption tool somehow has to pass decryption information to the OS on boot?
There would have to be some form of information transfer indeed, if the encryption cannot be done "underneath" the OS (either as above, or possibly using virtualization techniques – but then you sort of have two (or more) OSes running). And yes that means cross-OS is hard.
You'll also need the boostrap code (bootloader at the very least) to be un-encrypted if you don't have hardware/firmware assistance.
The Wikipedia disk encryption article has more about this.
If you have hardware (or more precisely firmware, i.e. BIOS) support for encrypted drives, then you can encrypt the full disk with the firmware. There are downsides to doing that: there aren't many computers around that support disk encryption, and it ties you to a particular firmware (or worse, if your computer has a TPM and the encryption key is in a TPM, it ties you to this particular motherboard unless you've backed up the storage encryption key).
If the operating system does the encryption, then there has to be a small space on the disk that is not encrypted, where the initial parts of the operating system are stored. A common configuration with Linux is to have a separate cleartext /boot partition, and to encrypt every other partition. “Full-disk encryption” is a bit of a misnomer: it's usually used to mean “full volume encryption”, where a volume is typically a partition rather than a disk. Full-disk encryption is when you don't encrypt every file (or at least a directory tree) separately.
Under Linux, the standard tool for full-disk encryption is dmcrypt. It is available in all major distributions and integrated in many installers.