It is perfectly legal. Phones are locked to a specific service provider because the SP subsidises the handset cost, to get folk to buy one and take up the service. And of course they don't want to subsidise a rival's service so they lock it to their network, so you will spend with them, And they get the money back gradually over from the cost of your calls.
Unlocking prices are very varied. Sometimes you can get info on the Net, but many markets can do it for you for a few quid. I don't think the charge is large enough to be worth too much shopping around for.