[Verizon Samsung Galaxy S 4] Cruiserdude:
Don't think I have to explain root, but custom recovery is just that, it's what you use to flash all sorts of things to your phone. That doesn't mean everything you flash will boot, however.

What we refer to as a locked bootloader is basically a security check in the boot chain. Typically, each step of the boot process will check the next component for a valid signing key. This key is encrypted and known only to the OEM, and it's not realistic to expect that it can be found, generated, or brute-force cracked. What this means is that at any point in the boot process, if the next component in line does not have a valid signing key, the boot process will halt. This means if you try to flash a different kernel, or a rom that includes one, the phone won't boot, since the developer could not have signed it with the OEM key. And if you try to flash a bootloader that has signature checking disabled, the loader that proceeds it in the boot chain will not allow the process to continue unless that bootloader has the proper key.

Unlocking the bootloader simply means you are disabling signature checking at some point in the boot chain, allowing you to boot a kernel that isn't signed with the proper OEM key. This can be done through basic adb commands on devices that are designed to be unlockable by the manufacturer, sometimes after getting a key from the manufacturer after registering your esn to have your warranty voided. Some devices come already unlocked, and then devices like ours and most Motos are locked and encrypted, with no method of unlocking provided by the manufacturer as of yet.

Such devices are often cracked, sometimes through software exploits at one of the stages in the bootchain, allowing us to disable, bypass, or spoof the signature checking process, and boot an unsigned kernel. (like ralekdev's Exynos exploits) Other times someone discovers a hidden "unlock switch" that the manufacturer has built in, either for engineering purposes or a future unlocking program, and figures out a way to trigger it. (like Dan's unlock method for the Razr HD/M) Sometimes there's a risky hardware hack, such as often proceeds less risky methods on HTC devices. Lastly, there's the possibility of a leaked bootchain component that has the proper signature but allows us to disable signature checking from that point in the boot process, such as happened with the S3.

Anyway, it's definitely preferable to have a true unlock, as it's then easy to flash a custom recovery, and any properly built kernel will boot just fine with no shenanigans required. However, there are typically ways to get a custom recovery up and running even with a locked bootloader. Often, you can only flash roms and not kernels in these cases, as they typically only modify the Java/smali side of things, that is typically not checked or easily spoofed on boot. But it's no fun being stuck on the stock kernel, especially when you want to build AOSP roms, or when there's a newer version of Android than what the stock software is. Not to mention that many of us want to improve performance, stamina, and hardware functionality, and this is mainly accomplished through custom kernels.

Sometimes, various exploits are found to allow an unsigned kernel to boot even with the bootloader still locked, and that's what Loki is (so are kexec, 2nd-init, etc). Not as good as a true unlock due to all the shenanigans required to get around the signature checking, but still the experience is typically the same once the device is up and running.

What concerns me is that this thread isn't specific on what requirements a custom recovery must meet. A recovery similar to what the OMAP Motos had until they were EOL anyway, that only let's you flash roms atop the stock kernel, doesn't allow the type of development many of us are expecting from a Samsung device. But one with a workaround that allows kernel flashing, just like Loki, is MUCH more valuable to us. Still not as good as a true unlock in actual usage, but again once the device boots it's basically the same. The problem is that Samsung/VZW have already shown that they are quite capable of patching such exploits with future updates, and for the first time ever on a Samsung device, they can prevent us from reverting back to the old, exploitable software.

That's the final and biggest reason why a true bootloader unlock is the real prize, and the only long-term solution. So let's all keep our fingers crossed!