A Deed Poll is a
declaration by a person that they have changed their name. It is an instrument of the laws of
England but is accepted without question by all departments, organisations and companies throughout the
United Kingdom, and will generally be accepted by any country that uses a British-derived legal system.
Under English law you can use any name whatsoever. There are no restrictions. You can call yourself George Orwell or Botty Bum Wee-Wees or Her Majesty Queen Elizabeth the Second, and no-one can stop you. If however you were born Reginald Dwight and have got a passport, bank account, driving licence and so on in that name, the passport agency, gas board, inland revenue and so on will all be deeply unimpressed if you merely mention that you've changed your name (or sex), and you'll keep getting bills addressed to Mr Dwight. They want solid documentary evidence that you've changed it. The Deed Poll delivers this. It does not change your name as such -- you can do that at any time, merely by using the new name. It is your declaration that you have entirely renounced the old name and will use the new name for all purposes, and is a legally impeccable document.
To get a bank account in the first place under a certain name you had to show the bank documentary proof of your name. The one document we all have is a birth certificate. This is proof of name. (It's proof of someone's name, at least.) To get a borrowing card at the local library you also need some identification, but they'll take a gas bill with your name on it. Banks have higher standards on this than libraries.
After you're born there are several events in your life which can change your name, and the certificates of which constitute proof of change of name: adoption; and the beginning and end of marriage. A woman has the right to adopt her husband's surname upon marriage, and to resume her former name at the end of marriage. Therefore a marriage certificate, a husband's death certificate, and a decree absolute of divorce all have the highest authority. No other name changes will be routinely accepted by all organisations you need to deal with, unless you obtain a Deed Poll. And note that under common law the only choice the woman has is keeping her surname or adopting her husband's: for either of them to adopt a double-barrelled or other combined name is not legally established by the marriage certificate, and requires a deed poll to make it uncontestable.
There is no central repository of Deed Polls (and the plural is probably Deeds Poll). There is only one copy of the deed: yours. You draw it up, sign it, get it witnessed, then send it to people you want to know about it, and hope they send it back. A solicitor can draw it up for you, or you can get a pack from a quango called the UK Deed Poll Service. You can go to a solicitor to send certified copies to organisations instead of the original. It costs extra to get the UK Deed Poll Service to keep backups for you; or to enrol it at the Royal Courts of Justice and thereby publish it in the official journal the London Gazette.
The name comes from the fact that the deed is "polled", cut straight, as opposed to "indented", cut or torn in an indented or sawtooth manner. An indenture was between two people (such as master and apprentice) and the irregular separation was a guard against forgery.
The UK Deed Poll Service do impose some restrictions on names they allow on deed polls. You can call yourself Princess This or Colonel That but they will not register it, nor anything else that seems to be a title of honour or rank; nor will they register obscenities or blasphemies; nor anything non-standard in names like numerals or punctuation beyond what is traditionally used (Armstrong-Jones, O'Brien). You need both a forename and a surname. They do allow "fun" names like Father Christmas or Donald Duck. They will also allow you to use well-known names like Elton John, since names can't be trademarked. The real restriction on names is that you cannot use a name for fradulent purposes: claiming that your name is Elton John is fine, but claiming or implying that you are the singer Elton John is actionable, as would be setting up the Elton John Music Shop.
You have to be 18 or over to execute a Deed Poll. Parents can execute for children, but children of 16 or 17 must consent. Both parents' consent is required for children, more or less no matter what the state of the relationship: even if the father has no contact, the shared surname is a link that cannot be removed without a court order.
A deed poll is an ancient device for making any one-sided declaration, and their use for changes of name is modern (only as far back as 1851), but today it is the only use, and a deed poll is always understood to mean a Deed of Change of Name.
On a related note, marital status and sex are legally well-defined. You're either single or married, female or male. This is naturally a point of contention for homosexuals, transsexuals, and others who don't like conforming to this stricture. You can use any name or title you like: calling yourself Mrs is fine on a document such as an application for a mortgage. The title "Mrs" has no legal implication. However, you are required to tick the box saying "single" or "male" if that's what you are in the eyes of the law.
UK Deed Poll Service: www.ukdps.co.uk