Unlocking a phone is not illegal, to my knowledge. It just removes the block that network operators add, which ties the phone to their network.
However getting it done is usually achieved most reliably by taking it to a shop specialising in such things. Buying unlock codes over the internet is not to be recommended, IMO.
There are several other internet sites which would probably be able to give better advice about unlocking.