Android - What does it mean to "brick" your phone?

The term "brick" usually refers to the stone, which means: "device can only be used as paper-weight". Taken literally, there's no way to "unbrick".

However, you also find terms like "hard-brick" and "soft-brick" used, which makes the term "brick" less absolute: A soft-brick is something you easily can recover from (count it as a "temporary paper-weight"), mostly by software-based solutions (e.g. re-flash your phone) -- while a "hard-brick" is rather meant in the way the original term points to.

Still, technically spoken, even a "hard-bricked" device could be "unbricked" -- but mostly this is more expensive then getting a new device.

As for the warranty declaration you quoted: For a normal user, it's almost impossible to (hard-) brick his device. Even when flashing a custom ROM, this can rarely happen, as there are many security-layers involved. Almost always you can boot your device into some fall-back mode where it is at least recognized by some "flashing software", so you could simply flash another/the original firmware back. Which means, the risk you are taking is to "soft-brick" your device¹. A "hard-brick" is quite unlikely with "normal operations" like rooting or flashing custom ROMs.

See also:

• Wikipedia: Brick
• RootzWiki: Brick

¹ I just learned: "Unless you've got a Samsung device and used the software recommended by Samsung". So better don't use Kies etc., but rather Odin, just to give an example.

Brick is a much-hyped word that gets bandied about without understanding what it is.

There's two types of brick, hard and soft. Let's go through this to make the distinction clearer.

• Hard - this is where the handset will absolutely refuse to boot at the press of the power button.
  Diagnostics: Dead screen, no power. That is the symptom of a hard brick.
  Reason: This can happen by inadvertently pulling the cable when flashing a ROM or even an update via the handset's supporting software such as Samsung Kies, Sony's PC Companion Suite etc. That is the worst case, that is why in this scenario, always, make, sure that no cable gets pulled unless told so by the supporting software in question. The other way is this, flashing in that manner when the battery power is low. Hence for that reason, it is recommended to have at least 75% of battery power in place prior to doing the update in that fashion. It's known as hard-brick, and requires specialist cables and stripping the device down to the circuitry board to revive it via JTAG cables.
• Soft - this can happen through a bad flashing of the ROM in which yields the following.
  Diagnostics: it has power when the power button is pressed, and/or, the screen comes on.
  Reason: It can be a user error on this part. For example, failing to clear/wipe the data/cache, can cause Android to go into a bootloop because of the mismatches with the Android's virtual machine and the apps installed, or more than likely, a corrupted dalvik cache. The other, is flashing a ROM that is not designated for the handset which can cause the kernel to go into a bootloop. This is generally easier to fix, but hangs, that is known as a soft-brick.

With those two separate forms of brick, it is generally speaking, a scaremongering tactic.

The one pure simple reason why carriers do not recommend unlocking the boot-loader, is not just for the warranty. It's more down to the fact, if the handset ever gets stolen, then unlocking the bootloader will wipe everything, and reinitialize the handset to factory state, thereby all your contacts, call logs, messages and apps gets wiped cleanly. Also, this is to reduce the amount of support in the carriers, with people calling in or ringing up the technical support, "What happened with my handset - I did something and lost my contacts?"

Just to finish off this answer, you can revert it back, by relocking the bootloader at a later stage if you wish, that is in the event the hardware got damaged and hand it back in for repairs.