It all depends whether you are on contract or Pay As You Go!
If you're on a contract you will have to pay off what remains of it before you can change.
If you are looking to change to a contract, its normally more sensible to get a new handset, since they are almost always free and then you get the years warranty.
If you are PAYG or your contract has ended, you can just get a new PAYG sim, normally either off the network providers website labelled "sim pack" or something similar, or from newsagents / phone shops / ebay etc. Cost about £5 - 15 depending on network and where you buy.
Also, depending on what network you are changing to, you may need to get your handset unlocked. This can be done at phoneshops, although normally the smaller independant ones not the chains, and the cost will be £10 - 15.