Toothed belt = timing belt.

You dont say what engine you have, but if its never been changed you should change it.

Cost should be around £300 - £400 depending on where you go and whats changed. Its deemed a good idea to change water pump at same time, which adds on £50.

I had mine done (belt & waterpump) last month on a Golf mk4 which cost £300.

'Toothed belt', also known as Cam belt.

As has been said, it's good practice to change the water pump at the same time, and also the 'toothed belt' tensioner pulley, as if either of these fails shortly after the belt has been changed, the job will have to be done again. If the auxilliary belt (drives the alternator, power steering pump, air conditioning pump) has to come off to do the job, then it's a good idea to replace that too.