What is tethered vs. untethered iPhone jailbreaking?

A tethered jailbreak requires the iOS device to be plugged into a computer when turned on. If the iPhone is not plugged into a computer and booted with special software the device will not enter a jailbroken state.

Untethered jailbreaks do not require a computer. Everything required to enter the jailbroken state is contained on the iPhone. Rebooting away from a computer does not affect the jailbreak. iOS 4.3.3 and older jailbreaks including PwnageTool, limera1n, greenpois0n and sn0wbreeze are untethered solutions.

Tethering with iOS 5 and redsn0w 0.9.9b7

iPhone 4S and iPhone 4 users will need to wait for new software that makes untethered jailbreaking possible.

Some iPhone 3GS models can be jailbroken untethered, while others can't at this time. Check if you have an MC model that requires tethering.