Tethered means being basically "attached" to your computer in a way; you must boot your device by running code on it (via the dock connector) to make use of an exploit. Devices are tethered because there is one or more area where the device fails one or more signature check along the way due to the jailbreak. The device is able to boot up because there is a way to execute code via USB that allows you to bootstrap to a pwned (no signature check) iBSS, iBEC, or iBoot to finish the boot process. To boot tethered, you need to use the software which you used to jailbreak and click "boot tethered"
Currently, certain devices are capable of booting to Linux. The downside is that this is a tethered boot.
In some circumstances, a tethered jailbreak can be made "semi-tethered." When a device is "semi-tethered," it can run most applications properly. However, some parts will refuse to operate as expected (e.g.- Safari may crash, you cannot use any programs from Cydia…).