The Dev Team has released their Pwnage Tool v3.1 for MacOS. This will jailbreak the new 3.1 and 3.1.1 firmwares by building a custom .ipsw. The tool only works on the iPod touch 1G, iPhone 2G and iPhone 3G. As yet there is not jailbreak tool for Windows or jailbreak for OS3.1 on the iPod touch 2G, iPod touch 3G or iPhone 3GS.
See the Dev Team’s blog post here for full details and downloads.
GOLDEN RULE: If you are using a 3G iPhone with ultrasn0w and rely on ultrasn0w to obtain cellular service, then you should only upgrade to 3.1 with a PwnageTool created .ipsw