% Namechange
See: http://www.transequality.org/documents/state/maine
This has information about how to change your legal name/ID, across various parts of USA.
https://www.scequality.org/public/files/docs/SCNameChangePacket-small.pdf
Name Change info: here
This is for UK *citizens* only. If you're resident in the UK, but not a citizen, you still have to go through your own government in the countr[y/ies] in which you are a citizen of. See: https://www.gov.uk/browse/citizenship/citizenship
Go to any decent solicitor and arrange to have your legal name changed via deed poll. You can also use this to get your legal title changed (E.g. Mr. to Ms., or Ms. to Mr., etc).
You don't have to get a lawyer to do it, you can do it yourself too. This page has a guide for it: http://bikkit.co.uk/deedpoll.html
If you do it correctly as per that guide (if you're doing it yourself without a solicitor) and the deed poll gets rejected, note that this is *discrimination* according to the Equality Act 2010. Your deed poll is equally valid whether you write it yourself or get it from a solicitor.
It's cheap, and anyone (even cis people) can do it, with little or no scrutiny. You then contact e.g. bank, utility providers, landlord / mortgage provider, etc to get your name/gender changed in their records.
See: https://www.gov.uk/change-name-deed-poll/overview
The UK government has guidelines: https://www.gov.uk/government/publications/applying-for-a-passport-information-for-transgender-and-transsexual-customers.
This can also be used to get a new passport, in your new name, with your gender marker changed.
You should present as your desired gender, in your new passport photo; basically, you should look in that photo like you think you're going to look the next time you need your passport (e.g. verifying your ID when you register a bank account, or go travelling, etc). So if you're a trans woman, present as a woman in the new passport photo. If you're a trans man, present as a man in the new passport photo. NOTE: non-binary people are not legally recognized in the UK; passports are only issued with M or F gender markers on them. This is a current issue in the UK, which ought to change (E.g. X gender marker on passports).
You can find photo booths (for taking passports) in or around most supermarkets or in shopping centres. These photo booths are often intended for the purpose of passport photos, and photos for other official ID in the UK.
You need doctors authorization to change your gender marker on your passport. This does not have to be at a gender clinic. You can just ask your GP to write a letter for you, and give you the letter, confirming that you are transitioning. NOTE (non-binary people): you can only change your passport to say either Male or Female. The UK does not legally recognise non-binary people at present, unfortunately.
Going through your GP is the fastest route, if you're on a waiting list (private or NHS, since both usually have waiting lists) for trans care.
Get your doctor (e.g. GP) to write something like this (substitute man/woman as necessary):
The letter from the doctor should say your *NEW* name, not your old one. So for instance, if you're a trans man and your new name is Gary Metcalfe, then the letter should say Mr. Gary Metcalfe on it, when referring to you. If you're a trans woman and you're new name is Annika Greer, the letter should refer to you as Ms/Mrs Annika Greer. (non-binary people are not legally recognised in the UK, and passports can only say male/female on them. This is something that we as a community need to campaign to change)
United Kingdom Passport Agency,\ London Passport Office,\ Globe House,\ 89 Eccleston Square,\ London,\ SW1V 1PN\ \ Subject: Mr/Ms/Mrs [Your First Name] [any middle names] [Your Surname]\ \ To whom it may concern,\ \ The above named is a trans man/woman (female-to-male/male-to-female) who [wishes to receive health services related to gender reassignment and is making strides to do so / is receiving private gender reassignment health services via [clinic] since [date]/ is receiving NHS gender reassignment services since [date]].\ \ I can confirm that Mr/Ms/Mrs [Your Surname] has made an official name change via deed poll process and has been living successfully in the male/female role.\ \ In my opinion the patient is stable and permanent in his/her chosen gender role and I would be grateful if you would issue a male/female passport to him/her in accordance with this.\ \ Yours sincerely,\ [Doctors Name Goes Here]
Deed poll only changes your legal name/gender currently in use, but it does not alter your birth certificate. It also does not alter your death certificate (if you die, your death will be recorded according to your birth certificate). If you go to prison, quite often they will send you to the wrong prison.
In 2004, the UK government started allowing transgender people to update their birth certificate, by letting them acquire what's known as a gender recognition certificate.
To get this, you must first complete the deed poll process, and you need to live full-time in your desired gender for at least 2 years, with proof that you have done so (name on mortgage/rent, utility bills, etc, and/or testimony from others). You usually also need an approval letter from your gender clinic, whether NHS or private.
See: https://www.gov.uk/apply-gender-recognition-certificate/overview.
New Zealand grants citizens the right to change their name/gender on passports and other documents. They also allow for X gender to be specified, in the case of non-binary trans people.
See: https://www.passports.govt.nz/what-you-need-to-renew-or-apply-for-a-passport/information/
Under the Births, Deaths and Marriages and Relationships Registration Act 1995, you can also change your name/gender on your birth record. If you're a child, your parents and/or guardians can apply to the New Zealand Family Court. Adults can change their details themselves.