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 version of iOS (5,0.1), as well as the iPhone 4S and iPad 2, can be untethered jailbroken already using Absinthe or Redsn0w.
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).
There are 2 types of untethered jailbreaks: Patched LLB-based and kernel hacks. On the first sort, that requires an untethered bootrom dump (e.g. 24kpwn or Pwnage 2.0), it is permanent and unpatchable, except for an hardware update. This type of jailbreak patches the LLB to not check the firmware at boot-up , letting a pwned kernel or a custom bootlogo to be uploaded to the system. The second type, uploads the unpwned kernel, the system checks the signature, then a kernel exploit happens and the jailbroken kernel is uploaded to the system. After the exploit, the bootlogo can be changed. This is how Greenpois0n's animate works.
Utilities capable of untethered jailbreaks
These jailbreak utilities can perform an untethered jailbreak, sorted by operating system.
Star and saffron run on the device itself, and are completely independent of a computer's operating system. JailbreakMe has supported so far 1.0-1.1.1,3.1.2-4.0.1(no 3.2.2) and 4.3-4.3.3. Each device can be jailbroken on those firmwares, No matter what, but if SHSH blobs aren't given for a certain firmware, it is not restorable.