A bootloader is a computer program that loads an operating system (OS) or runtime environment for the computer after completion of the self-tests.
The bootloader configures the device to an initial known state and has a means to select where to start executing the kernel. It can allow you to make this selection, which give you for example the opportunity to start an alternative Linux kernel, or Windows. Because the bootloader is an essential component of the boot process, it is stored in non-volatile memory, such as flash memory.
Bootloaders are written by hardware vendors and are specialized for the hardware they run on.
For Android devices, the bootloader typically starts either Android or Recovery. Android bootloaders often have a basic interactive mode that can be triggered by holding the "volume down" button while the bootloader is executing.
A locked bootloader is one that will only boot an OS that it "approves" of. This may mean that device's boot partition has an approved digital signature, or the carrier ID (CID) hard-coded into the OS matches a value hard-coded into the bootloader itself. See also Wikipedia:Hardware restrictions#Verified/trusted/secure boot and Wikipedia:SIM lock.
For devices with a locked bootloader, booting an unsanctioned OS (e.g. CyanogenMod or Ubuntu) requires the device's owner to first unlock (or even replace) the bootloader. Unlocking the bootloader sometimes voids the device's warranty. Procedures vary typically by manufacturer. (XDA)
Bootloader unlocking should not be confused with Android rooting.