They can lock your phone to a specifik network (like the ones mentioned) or they can lock you phone to a specifk sim card so that only that one works.
There are many, many unlocking sites on the net.
I unlocked my siemens m35 using a proggie found on the net and a data cable.
[off topic]
This phone (siemens m35) is btw vulnarable to a DoS attack by sending a specially crafted sms to it. (there are more siemens phones vulnarable).
[/off topic]

In my country (the netherlands) the gvt has made unlocking a phone illegal. Due to the fact that the software is copyright and it is forbidden to reverse engineer it.
Some guy running an unlocking service got fiend for 5000 euros (approx 5000$).
Just thought you should now.