My verizon iphone 4s works CDMA on verizon, and GSM everywhere outside the US (you can ask verizon to unlock it for use outside the us 60 days into your contract. you should, if you haven't yet)
First, you have to be in good payment standing on your plan, and a customer for at least 60 days. Assuming that's already the case:
Call them up on 611, and say you're going to go abroad soon, and you would like to unlock your phone for non-US use. They will ask you to confirm a bunch of things, some sillier than others (That you know this does NOT give you a way out of your contract; that you may NOT use the phone to do anything that's illegal in the US, wherever you do it; I don't remember the whole thing). Then they say they're processing it, and will tell you that in a couple of hours, you should either log in to the itunes store on the phone, or do a sync with itunes to receive the new profile. After you do that, you restart your phone, and it will accept non-US sim cards.
Things might have changed about the process since I've done it; I heard from some people that they had to log in to itunes with the new sim inside in order for it to be approved. The verizon person will guide you through the current requirements.
