What kind of iPhones? If they are 3G then you can unlock them with ultrasnow in Cydia on 3.1.3. As of now, if you are using a 3GS then ultrasnow won't work
So yes (if they are 3G), if you click restore it will update the firmware to 3.1.3, then you would jailbreak with spirit, and unlock with ultrasnow, and it should be unlocked for use with other carriers.
If they are 3GS, you are going to have to stay at 3.1.2 firmware. This would involved having your SHSH backed up, restoring the 3.1.2 firmware via iTunes, and jailbreaking with spirit and unlocking with ultrasnow (I think). I'm not completely sure on the process to do that, so hopefully someone else can offer some input if your phones are 3GS.