Check for SHSHs. Use TinyUmbrella. If you have SHSHs for 4.1, it can be done with a custom firmware via PwnageTool. If you don't have a SHSHs you can go to 4.2.1 too with a custom firmware to preserve your baseband and keep the unlock. It will be untethered since you have an old boot.
Edit: 4.2.1 will be fine for your device and shouldn't present much problems, but if you have SHSHs you can go to 4.1 if you want. If you don't have SHSHs, you can stay on 3.1.3 if you're worried about issues on 4.2.1, but being the old boot 3GS I don't think it'll be an issue.
To get to 4.2.1, with the old boot there are a couple special instructions so check out the dev team's blog for those.
Last edited by i.Annie; 01-28-2011 at 06:05 PM.
Reason: Automerged Doublepost
Then 4.2.1 via custom firmware (PwnageTool created) is your only option if you need to maintain unlockability.
Basically to sum it up you'll be restoring to a cfw without the iPad baseband. That'll take you to 4.2.1, then you'll need redsn0w 0.9.6rc8 to complete the jb and install Cydia