Unlocking a phone is fairly trivial in my experience. You just need to get the unlock code from the carrier and enter it on the phone. I know Tmobile will give you the unlock code without much trouble if you are off contract.

Buying an unlocked handset may be your best choice. I don't really have any recommendations other than to make sure that it is GSM and the frequencies (both call and data) match the standard in the destination country. Something like the n8 - which is a pentaband phone - would have a high probability of working most places in the world.