What is "root"?
I needed some time to understand what "root" really means. It is quite simple:
Your phone is "rooted" when you have a "Superuser" app successfully installed.
The problem is that you need "Superuser" rights to install a "Superuser" app... To break that tie the Superuser app is usually installed as a zip file using a "recovery software". You can download the latest Superuser zip file from ChainsDD's site here or Chainfire's "SuperSU" here.
What is "recovery software"?
This is the software that is usually used to install updates on your phone. It is present on every phone and can install zip files. You can start the recovery software by pressing a special key combination while powering the phone on. This varies from phone to phone. Google how it is done for your phone.
The stock versions of the recovery software only install zip files that are digitally signed by the manufacturer, so they don't accept the Superuser zip file. That's why you usually have to replace the stock recovery software to install the Superuser zip file.
This is where "locked bootloaders" add an additional problem to the whole procedure: they don't allow you to replace anything on your phone. That's why you first have to "unlock" the bootloader on some phones.
The most common recovery software is created by Koush and is called "ClockworkMod". The official download site is here. You install the recovery software using the fastboot utility from the Android SDK in bootloader mode (again a key combination while powering on) with this commandline:
fastboot flash recovery recovery-clockwork-version-devicename.img
If you don't want to overwrite your phone's original recovery software you may try to only boot the recovery by entering
fastboot boot recovery-clockwork-version-devicename.img
To install the Superuser zip file copy it to the phones SD card/USB storage, start/boot the recovery software and choose the "install zip file" option.
Samsung phones (except Nexus models) don't support fastboot. You must use ODIN or Heimdall to flash a new kernel. Best option I found so far is Chainfire's "CF-Root" kernel. Look at xda-developers for downloads. These kernels also contain a version of the ClockworkMod recovery.
What is "S-ON"?
HTC phones have an additional protection. So even when you have Superuser installed it is impossible to write to some areas of your phone in normal operation mode. In this case installation of system stuff is usually done using the recovery software.