Call them. You're supposed to get the money refunded automatically, but you won't get far trusting the efficiency and generosity of the Inland Revenue. I prefer to send letters, just so there's a paper trail though.
When you call them, make sure you've got all relevant documentation in front of you (i.e. all of last year's pay slips and your P60, if it's arrived.) Any overpayment of tax will be refunded by cheque, and can be claimed anytime up to six years later.
Once you get your P60 sent it (the original- keep a copy) to your tax office with a letter quoting your NI number & telling them what you were doing from 6 April 04 to the date you started that job. If you weren't working, say what you were doing (student/ SAHM/ signing on) and whether you were claiming any benefits (not tax credits). That way they have all the info to hand & don't have to waste time writing to you to ask.
(sweetheart- it's your employer who calculates your pay every month/week, not the IR...)