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.
Devices as new as the iPhone 4/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 kernel is being patched and changed to fit jailbreak. After the exploit, the bootlogo can be changed. A userland exploit was used before the kernel exploit to get bypassed the iBoot signature checks before the kernel exploit. up to iOS 4.3.3, Incomplete Codesign Exploit was used. in iOS 4.3.4, it was patched. in 5.0.1 Racoon String Format Overflow Exploit is used instead. The kernel exploits found so far: BPF_STX Kernel Write Exploit (works up to iOS 3.2), iOSurface Kernel Exploit (works up to iOS 4.0.1, excluding 3.2.2), Packet Filter Kernel Exploit (Works up to iOS 4.2 beta 3), HFS Legacy Volume Name Stack Buffer Overflow (vulnerability in HFS, works up to iOS 4.2.8), ndrv_setspec() Integer Overflow (Works up to iOS 4.3.3) and HFS Heap Overflow (Works up to iOS 5.0.1)
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.