IPhone – Upgrade iPhone 4G from iOS 4.1 to any iOS

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 not yet a readily available iOS 4.1 jailbreak. Your best bet is to jailbreak using jailbreakme.com and stay on 3.1.3. With the baseband in 3.1.3, you can still install ultrasn0w (required to unlock and work with any GSM provider)

Once the iPhone Dev Team has published an update to pwnagetool that works with iOS 4.1, it will be safe to upgrade. You can currently unlock iOS 4.1 with redsn0w, but that DOES NOT allow for unlocking via ultrasn0w.