If you are going to reside in many different locations in the world, and not travel outside the major cities on the States…
[ul][li]Get an unlocked* triband or quadband"* GSM phone. [/li]
[li]Get a phone number in the States. Make sure that you can forward your calls internationally from this number, and that you can change the settings on this number from overseas. [/li]
[li]Get a local cellphone account with a local phone number in each location where you reside. The local account will come with a SIM card that you can insert into your phone. [/li]
[li]Forward your US number to whatever your local cell number is. [/li]
[li]Maintain your US number as a permanent contact point. People can still call your local cell number.[/ul] [/li]Note: if you are going to Japan, you will have to get a Japanese phone, as Japan does not use GSM***, and uses a completely different frequency band than the rest of the world.
Mind you, if you’re only moving every three years, phone models will change so much between each move that you may want to get a new phone anyways, as stankow mentioned.
If you were moving from country to country every few days or weeks, you would be better off with an account at a carrier with a lot of GSM “roaming agreements”, which let you use your phone on foreign systems without needing special arrangements or an account with the foreign carrier. But roaming is a lot more expensive than getting a local account.
If it’s a work phone, check to see whether your future employer can provide you with similar service to what I’ve described, or at least can provide an account on a local carrier in your place of posting. (The US Foreign Service has got to have some influence… 
)
*Unlocking
Many cellphone companies subsidize their phones so that the user pays a low price for them. The additional cost of the phone is made up through the monthly fees for the phone service. The carriers place restrictions in the phones themselves to prevent the user from taking the cheap phone to another company. This is called “locking” the phone.
In the US, such restrictions have traditionally been enforced at by differences in network technology between carriers. However, with the conversion of many US carriers on GSM network technology, there is now more oppurtunity to take a phone to another company and have it work.
If you want to pay full price for a phone, you should be able to get a GSM phone that is free of all such restrictions. The phone will cost several hundred dollars US.
Unfortulately most US (and Canadian) GSM carriers (ATT Wireless, Voicestream, Cingular, plus various local and regional carriers) are less than clear about the restrictions on a particular phone. Questions to ask:
“Is this phone completely unlocked?”
“If this phone is subsidized, how can I pay off the subsidy and get it unlocked?”
You can be sure, however, that the phones they’re selling for 49.99 or less with a two-year contract are locked …
**frequency bands
GSM cellphones in most of the world work on 900 and 1800 MHz. GSM cellphones in North America work on 1900 MHz, although the carriers are rolling out GSM on 850 MHz as well.
To travel the world, you need a phone that works on at the least 1900 and 900 MHz, as the OP mentioned. A ‘triband’ phone will work on 900, 1800, and 1900 MHz, giving you a greater choice of carriers in Europe (the 1800-MHz carriers are sometimes cheaper).
A quadband phone will work on the 850, 900, 1800, and 1900 MHz bands. I know of only one that has been announced so far, the NEC 515. I don’t know whether it’s available yet.
<nitpick>
Baron, world phones such as the T28w are dual-or tri-band, not dual-mode.
A multi-band phone use the same network standard on more than one frequency. This is similar to the way radio stations can broadcast at 99.9, 102.1, and 107.1 MHz… but all use FM.
A dual-mode phone can use more than one network standard, which is like a radio receiver than can pick up both AM and FM stations.
</nitpick>
***I’m ignoring the third-generation stufff here.