Regarding the unlocking, some U.S. service providers will not unlock the phone for you -- I used to work for AT & T Wireless before it became Cingular, and had a phone paid for by my work, which they wouldn't unlock for me. However, T-Mobile, with whom I had my personal phone contract, was great -- I just phoned them up and explained that I would be travelling overseas for an extended period of time and that I needed my phone unlocked. They did it straight away. I would try contacting your carrier first to see if they can unlock your SIM. If not, there are many Web sites you can search for the unlocking codes -- with these, you just have to type in a series of numbers to get the phone to unlock.
My old phone was a GSM tri-band Samsung, and that worked just fine with an Orange SIM card in the UK. When I returned home, I bought a new Samsung phone, which is dual band, and the guy at the T-Mobile shop told me that it should work in the UK as well, should I ever decide I want to use it over there. I haven't tested it out yet, but he said dual band is all you really need if you're going overseas.
Many of the phones have dual voltage plugs as well, which is handy -- all I needed was a plug adapter for my phone charger and I was sorted. You can purchase a set of plug adapters for different continents at Radio Shack at a reasonable price -- it's handy to have the different plug adapters in case you travel a bit.