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.
Devices as old as (or older than) the iPhone 3GS with the old bootrom have known bootrom exploits, so PwnageTool can be leveraged to break the device's chain of trust. Newer devices, which include some iPhone 3GS units, as well as all "MC" model iPod touch 2G units, iPod touch 3G units and any subsequently released devices, contain bootroms that close the utilized exploit. limera1n has a bootroom exploit that can jailbreak iPhone 3GS and iPod Touch 2G MC models.
Star runs on the device itself (not a computer program), so it is completely independent from a computer's operating system.
PwnageTool can only be used on Mac OS X.