Since Apple has changed the upgrade mechanism, all we get right now is PwnageTool for Mac OS X, without support for iPhone 3GS, yet. There are also a couple of rules you should when using the jailbreak, so be sure to read after the break to learn them:
If you’re using ultrasn0w, you must use an ipsw created with the aid of PwnageTool, not the direct iTunes upgrade. Keep in mind that if you’re an iPhone 2G user, the unlock works directly with PwnageTool, while 3G owners will have to use PwnageTool-created ipsw. Remember to read all the right instructions, before starting the process and to backup your data.
iPhone OS 3.1 jailbreak only works on iPhone 2G, 3G and iPod Touch 1G, but if you want more info, this link is pure gold for you. Read it carefully!