All the guides that I can find online refer to the Windows-only "Odin" software. I also found an open-source alternative "Heimdall" but the Samsung S6 is not supported (and apparently it's not compatible with the .tar.gz file format).
I have installed WinXP on a VirtualBox virtual machine, and then I installed the Samsung USB drivers and the Windows Odin software. I then made sure to route all Samsung USB devices to this virtual machine, but still neither Windows nor Odin sees the phone - neither in its normal operating mode nor in its "Odin" download mode.
Chainfire's CF-Autoroot also uses Odin, which means I'm still stuck at the above problem. I also tried running Odin in Linux (using wine) but again it couldn't see the phone, and I didn't expect it to work anyway).
I have not been able to find a description of how to root the S6 (or any Samsung) directly in Linux, or via virtual machine. Is that simply not possible? Do I really need to install my old WinXP license on a physical computer?