An untethered jailbreak is a type of jailbreak where your device does not require you to reboot with a connection to an external device capable of executing commands on the device.
Many device/firmware combinations can use an untethered jailbreak. The most current versions of iOS (3.2.2 and 4.1), as well as the iPod touch 4G, can be jailbroken already with limera1n or greenpois0n.
Devices as new as the iPod touch 4G/Apple TV 2G have known bootrom exploits. However, the iPhone 3GS (old bootrom) and older have bootrom exploits that allow for an untethered jailbreak. Newer devices as old as the iPhone 3GS (new bootrom), iPod touch 2G (new bootrom), and iPod touch 3G have bootrom exploits that are limited to a tethered jailbreak (without the assistance of a firmware-based exploit).
Utilities capable of untethered jailbreaks
These jailbreak utilities can perform an untethered jailbreak, sorted by operating system.
Star runs on the device itself, and is completely independent of a computer's operating system.