I love my iPhone-4 and I am about to move to Mexico where AT&T and Verizon are not viable carrier options. What is the safest way to unlock my iPhone so I can continue to use my apps (and new ones I may acquire later) with a non-Apple approved carrier?
Do you mean to Jailbreak your phone, or to unlock it so you can use it on a different network?
Unlocks currently depend on your firmware version, which you can check by going to settings >> general >> about and looking at the version number. If you can confirm then we could find the right unlock for your phone, supposing it can be unlocked.
In the UK SIM lock is removed by the carrier themselves, for example O2 customers can simply request that their iPhone be unlocked online. I have done this with my original, 3GS and iPhone 4 and as such they can all be used on any GSM network and receive official software updates from Apple.
For AT&T iPhones it appears they are not offering a similar service to their customers in the US and you may need to resort to other means to unlock the device.
O2 UK iPhone Unlock: http://shop.o2.co.uk/update/unlockmyiphone.html