I have got a 16GB 3GS. it is currently running on 3.1.2 os. I have jailbroken it many times with blackrain but the icons doesn't appear after it restarts. But other than that it works great. though i need cydia to crack the youtube and maps apps that are disturbed by the unlock. So please if anyone knows then help.
Apple iPhone 3GS is really a cool phone and if you have this thats great. As far as how to jailbreak there a lot of blog which explains it manually and step by step. Go and check it