How to unlock an iPhone 3G with 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.