knoydart: Most UK handsets are unlocked when you buy them. Some are still (dealing with a friend who bought a San Francisco Android from Orange UK and is unable to unlock it at the moment here in nz) but rarely in my experience. Your local Carphone warehouse or similar store will help you. PAYG sims are just about given away and handset subsidises for contracts are pretty good by NZ standards if your happy to be locked in for 18 months - 24 months. I bought my mum a basic candybar nokia for the equivalent of $40 at the end of May, and you might pay upwards of $120 for a handset here in DSE or JB Hifi.
Not sure about this, all the major carriers lock all the headsets. Orange/Virgin/O2/T-Mobile/Vodafone.
Their are places like car phone warehouse that sell unlocked phones but it is almost always cheaper to buy the locked handset and unlock it rather than buying straight out unlocked phone.