if you want to keep 3.0 which many apps stopped supporting but here ya go
http://www.iclarified.com/entry/index.php?enid=4448
CBillups1
you can either use the above or upgrade to 4.1 nothing else can be used if you haven't saved shsh blobs!
Also, if you have the newer bootrom, will this provide an untethered jailbreak?
All 3GS with 3.0 have the old bootrom.
To OP, use Redsn0w to pwned(accepts custom firmware) JB the 3.0 firmware. Afterward, from now onward, if want to upgrade the firmware, create or search (google) for custom JB firmware (one that keeps the very stable 4.26 baseband). Then, restore with that custom firmware through ITunes.
Really, I thought that after week 40 they had the new bootrom that was not able to have an untethered jailbreak.
http://www.iclarified.com/jailbreak/iphone3gs/mac.php?firmware=3.0.0
Look at the bottom of the page. This from the jailbreak tutorial after I clicked on 3.0 firmware. Is this not the case?