A device with a tethered jailbreak has to be plugged into a computer while booting up, so that a jailbreaking program (like redsn0w) can help the device boot up jailbroken. It is called a "tethered" jailbreak because your device has to be attached to a computer to boot up properly.
When a device is booting, it loads Apple's own kernel initially, so a jailbroken device must be exploited and have the kernel patched each time it is booted up.
An untethered jailbreak includes powerful enough exploits that if the user turns the device off and back on, the device will start up completely, and the kernel will be patched without the help of a computer – in other words, it will be jailbroken after each reboot.
But a device with a tethered jailbreak is only temporarily jailbroken during a single boot of the phone. If the device turns off and then boots back up without the help of a jailbreaking tool, the device will no longer be running a patched kernel, and it may get stuck in a partially started state. In order for it to start completely and with a patched kernel, it essentially must be "re-jailbroken" with a computer (using the "boot tethered" feature of a jailbreaking tool) each time it is turned on. All changes to the files on the device (such as installed package files or edited system files) will persist between reboots, including changes that can only function if the device is jailbroken (such as installed package files).
A device with a tethered jailbreak may be able to have a semi-tethered solution, which means that when the device starts up on its own, it will no longer have a patched kernel (so it will not be able to run modified code), but it will still be usable for normal functions. With a semi-tethered solution, the user can also choose to start the device with the help of the jailbreaking tool in order for it to start with a patched kernel (jailbroken).
In more detail: Each iOS device has a bootchain that tries to make sure only trusted/signed code is loaded. A device with a tethered jailbreak is able to boot up with the help of a jailbreaking tool because the tool executes exploits via USB that bypass parts of that "chain of trust", bootstrapping to a pwned (no signature check) iBSS, iBEC, or iBoot to finish the boot process.
Using a tethered (or semi-tethered) jailbreak
To boot tethered, you need to plug your device into a computer, open the software that you used to jailbreak it, and find its tethered boot option. For redsn0w: click "Extras" and then click "Just boot".
If you don't boot tethered when you boot up the device, the device will either be (A) stuck at the Apple logo or (B) boot up into a seemingly "un-jailbroken" state where Cydia, Mail, and Safari crash (and jailbreak-only tweaks/themes don't work) - until you plug the device into a computer, open your tethered boot program (for example redsn0w), and follow its instructions. The situation in (B) is often called a semi-tethered jailbreak.
Tethered jailbreaks behave semi-tethered by default. If you install Mobile Substrate extensions (tweaks), your device will still be semi-tethered. But if you install Notification Center plugins that don't depend on WeeLoader, your device will no longer be semi-tethered – unless you also install the BigBoss semitether package.
Tethered jailbreaking tools
redsn0w and sn0wbreeze are permanently able to use limera1n and other bootrom exploits to jailbreak older devices tethered on any iOS version (including iPhone 3GS, iPhone 4, iPod touch 3rd generation, iPod touch 4th generation, iPad, and Apple TV 2G), because bootrom exploits take advantage of code that is permanently embedded in the device's hardware, which Apple cannot update with iOS updates. Those tools do usually need minor software updates (not exploit-related) to explicitly support new iOS versions. They also use additional exploits (specific to each iOS version) to produce untethered jailbreaks when possible.