I have an AT&T iPhone 3GS, and am wondering if I should switch to something else for use when visiting other countries.
CDMA only found wide acceptance in the US (licensing issues, primarily; major networks running on this being Verizon and Sprint. You should check with your operator (if it runs a CDMA network) but there's a good chance the country you're travelling to won't have any networks running on this standard; even if there are then roaming agreements could be lacking.
GSM is the more widely-adopted standard; practically every mobile phone operator outside of the US runs on this. In the US, AT&T and T-Mobile are GSM networks. Still, even if you have a GSM phone, there is one thing you need to watch out for. Even though the standard is the same, GSM mobile operators in different parts of the world use a different frequency bands. Again, the difference is mostly USA (850 / 1900 MHz range) vs Rest of the World (900 / 1800 MHz range). Here's a useful map showing what GSM frequency band is used in which country.
Having said that, most modern phones support multiple GSM frequency bands. If your phone technical specification says it is 'tri-band' or 'quad-band' then you're good because out of the four ranges in use, at least one in each region will be covered.
That's the technical part. In addition to that, as Ginamin pointed out in his answer, you might need to check with your operator whether the phone needs to be 'unlocked' to allow you to insert a local SIM and/or whether you have to subscribe to a roaming plan.
The USA is a special case here. In nearly every other country, GSM & SIM cards are the only type of mobile phone network used. Most mobile phones you buy are 'locked' so they only work with SIM cards from that mobile phone network. You can 'unlock' phones.
Make sure your GSM phone is unlocked so you can put another SIM card into it, and you can use your phone almost anywhere.
In some territories, phone companies are legally obliged to unlock your phone so you can use it on different networks within that country, or abroad. Some phone companies will do it by custom X years/months after you got the phone. Some independent phone repair shops will unlock a phone for about €10. The older or more popular a phone is the more likely you are to find a place that can unlock it.