3.1.2 can be easily jailbroken using PwnageTool or blackra1n. Some people with newer 3GSes have a tethered jailbreak because of a new version of iBoot (not due to 3.1.2...if you have an untethered jailbreak now, you will have an untethered jailbreak on 3.1.2).
Not sure why you mention Cydia and Icy in your title, since your post is about jailbreaking in general, but I would like to point out that Icy has been abandoned by its developers and is no longer supported, developed or updated. Geohot already removed it from blackra1n, though it is installable from Cydia.