IF your iPhone has been jailbroken before, you can jailbreak it again even with the new OS. Otherwise you can downgrade, but it's difficult. Get someone who's done it before to do it, or else just wait until they figure out how to do it without the downgrade. It won't be long.
It depends on what bootrom you're using-- at one point not long after the 3GS was released, Apple changed the 3GS bootrom to prevent certain types of jailbreaks, so there are basically two versions of the 3GS our there, and you have to know what version you have before you start to jailbreak. If you have the old bootrom, you can use pwnage tool. If you're using the new bootrom, not only can you not jailbreak right now, you can't roll back your OS version either. So, you might have to sit tight. Now that jailbreaking isn't a crime, there will be new jailbreaks released soon.