Do I need to update to JB 3GS running 3.1?

Obvious n00b here looking for advice...

I've attempted to JB using sn0breeze and redsn0w with zero success. From what I have gathered, 3.1 isn't even supported by the most recent JB software out now.

Any advice as to which OS I could/should update to so I can JB it? I've had this phone for >2years and have only updated it maybe once since I bought it...

3GS can run everything up to 5, though most people stick on 4.2.1 because it seems to run better. redsn0w / sn0wbreeze are iOS specific. The latest version is NOT backwards compatible. If you want to JB an earlier version, you'll need to find the version of redsn0w that corresponds to it. Just google "redsn0w iOS <your version here>" and the first three results will usually confirm the version you need.

Worth mention that on the 3GS if you don't have SHSH, you can only restore to 5.0.1, but there is an untethered jailbreak (Corona/racoon) for 5.0.1 so you're good to go from the jailbreak front.