IPhone – Is it possibe to upgrade and re-jailbreak (in order to unlock) a 3Gs running on 4.1

My understanding is that there currently is not one, although rumours abound that one is coming up soon. The best place for "official" information is the iPhone Dev-Team. More direct/recent updates can be found by following various team members on Twitter. MuscleNerd is a good example. If other legitimate groups released anything solid, you will hear about it through them anyway (as is the case here: Chronic Dev Team seem reliable too). There are already fake sites springing up in anticipation of the next release; the important thing is not to use anything that hasn't been confirmed by them or that you have to pay for.

Additionally, if you have saved your SHSH blobs using Cydia on an already-jailbroken phone or The Firmware Umbrella, you can downgrade and jailbreak the old version. Normally this means you can upgrade using PwnageTool without losing your jailbreak, although I don't think the Dev-Team has released something compatible with 4.1 yet.

UPDATE

There is now a full jailbreak for 4.1 and later on 3GS. BigBoss maintains a jailbreak table which may be useful for updates at-a-glance. My understanding is that all current devices are now able to be jailbroken forever (greenpois0n/limera1n exploit), but iPhone 4 and later model 3GS are sometimes tethered on iOS new releases (as of this edit: not tethered on 4.1, but currently - hopefully not for long - tethered on 4.2)

There is nothing special to upgrading when jailbroken or not. You must use the official upgrade path which means losing unlock and jailbreak, and then re-jailbreak and re-unlock if you want and if it is possible with the new firmware. So...

1. Plug it in
2. Follow the prompts in iTunes