I have an iPhone 3G with 3.1.3 firmware. I want to upgrade it to 4.1, but I can't find information on how to then jailbreak it (I want it to work with any mobile provider).
Is there a way to jailbreak iOS 4.1?
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.