This is how I changed my legal name in Madison County, AL. The process is definitely different elsewhere.
I originally did this in September 2020 but I try to keep this info up to date based on feedback. Email me at tris@tris.fyi or ping me on Discord ("trisdoesnothaveausername") to give such feedback; I really appreciate it!
Background
In most (all?) jurisdictions in the US, only a court can legitimize your name change. Getting a court order will likely always be the easiest way to change your first or middle names regardless. There is a concept of a "common law" name change but in many cases it's not worth pursuing.
In Alabama, probate courts local to each county have the authority to issue an order to change your name. You get such an order by filing a petition to the court. The form for the petition is usually available on each court's website.
Getting the court order
In Madison County, as of October 2023, the form to petition the court is available online. It's a fillable PDF so you shouldn't have any trouble with formatting, etc (this was not always the case).
I specifically included "gender identity" in the "reason you are requesting a name change" space and had no issues.
After filling the form, it needs to be notarized. Many banks offer notary services; Redstone FCU offers theirs for free for members. The notary needs to watch you sign and date the document, and only needs to notarize the page with the notary declaration. The background check authorization only needs to be signed by you.
While I was at the bank I also got an official check to pay the filing fee ($37 at time of writing).
With the notarized petition in hand, I went to the courthouse. I also brought a photo ID (my drivers' license) and a certified copy of my birth certificate. You may be asked for proof of Madison County residency if your photo ID doesn't have your address on it. The probate court operates out of the Madison County Service Center at 1918 Memorial Parkway NW. They are open from 8:30a to 4:30p on weekdays. One of the clerks made a photocopy of my license and birth certificate (they did not need to keep the original birth certificate, this seems to be the norm, you should be able to ask for it back if they do try to keep it) and kept the petition + filing fee check. My name change was not set for hearing (this seems to be the norm).
Less than two weeks later I got three certified copies of the order in the mail. I took a picture of one for reference, but you should only need the case number to get more certified copies.
As of 2022, a few folks have mentioned that this process seems to be taking longer, so if you don't receive your name change order in the mail after a few weeks, don't worry. If your petition is rejected you should receive a letter explaining why (although this is very rare and usually only happens if there are issues completing the background check).
Changing your name with SSA
You need to change your name with the Social Security Administration before most other agencies. I filled out a SS-5 Application for a Social Security Card and mailed it to my local Social Security field office along with the name change order and my original driver's license.
You can and should do this process in person. If you make your application by mail, you must mail an original identity document to SSA. I had to order a duplicate drivers' license ($31.25) so I had something to drive with in the meantime. SSA does not need to keep an original drivers' license if you visit them in person, they just need to see it once.
To speed up the drivers' license process, try to get a "snap" temporary card on the day you visit SSA.
About two weeks later I received my license and court order back in the mail. A few days after that I received a receipt saying that I had applied for a Social Security card (this is the document you need to prove your name has been changed with SSA). A day after that I received another receipt (not sure why). About two weeks after that I received a new Social Security card in the mail.
If you do this process in person, you should get a receipt on the same day; just wait 24 hours after this to continue the process with ALEA so all of the computers involved have consistent information.
Changing your name with ALEA/on your driver's license
This used to be possible to do at any county license commissioner's office, including the Madison County Service Center.
As of August 2023 there are reports that name changes on drivers' licenses must be done at Church St. / an ALEA office, specifically for folks with REAL ID-compliant credentials (you have one of these if there's a star in the upper-right corner of your license). We are not exactly sure what is happening here, but consider calling the license office you're planning to visit ahead of time to confirm they can handle your name change.
I brought my current license, court order, and SSA receipt. You will need to pay $36.25 in real cash (cards are not accepted as of October 2020) for a duplicate license if you're not within the renewal window.
As of November 2023, there are reports that you may also need a Social Security card (your old or new one should both work) to change your name, so bring that too if you have it. The receipt alone might not be sufficient, especially if you have a REAL/STAR ID, but a "snap" temporary card should work.
I updated my title and vehicle registration at the same office. They needed the court order and my driver's licenses to do this. There is a fee for a corrected title but it was less than $30.
My new permanent/full-validity license was mailed to me in about three weeks.
Changing the name on your voter registration
I was able to change my name on my voter registration online the day after I changed the name on my driver's license. You can do so at the Secretary of State's website in Alabama. The name on my voter registration was updated a few days later; I received a new information postcard about a week later.
Changing your name with Selective Service
If you are a "male" aged 18-25 you need to update your name with the Selective Service. I mailed the registration card they sent me back to them with corrections. After ~3 weeks they sent a letter back asking for me to mail them a copy of the court order. My name was changed in their records online about a week later. Although I included a SASE for them to return the court order, I did not receive it back (I got someone else's status information letter in the envelope instead). Very cool.
Changing your name with car insurance companies
Geico let me change my name using their mobile app. I did not need to include documentation or even touch a computer. (This is probably because they pull your drivers' license record whenever you change this information, so make sure to only do this after you have a new license.)
Changing your name with banks
It seems easiest to change your name with any banks you do business with in person, if possible. I brought my court order, both my drivers' licenses (still using the interim/paper one), and my SSA receipt to the Wynn Drive Redstone branch and they were able to change my name on everything pretty quickly. They issued a new debit card immediately while I was there.
If you have a mortgage you should email the mortgage department at your bank as well. Redstone's needed to file my name change order separately from the rest of the bank but did not need any other information.
Discover let me change my name online by sending a "secure message" online. I needed a scan of my drivers' license and court order. They sent me a new card in a few days.
I did have some trouble changing my name with Betterment; they needed the full-validity license in my new name to change their records. Their email address is support@betterment.com.
Changing your name with Huntsville Utilities
I visited the physical Huntsville Utilities office downtown and spoke with a customer service representative. They gave me a form to fill out and needed to see my court order and drivers' license. The name was updated online a few days later.
Changing your name with your employer
I emailed a scan of the court order and SSA receipt; it was changed in payroll the next day. I needed to re-sign my IRS Form W-4 and direct deposit authorization. YMMV.
Changing your name with BCBS
I have health insurance through an employer-based plan with Blue Cross Blue Shield of Alabama. After changing my name on payroll I had to email BCBS separately with a copy of the court order using the "Message Center" on their online site. You can also change your name here through your employer but it may be easier to just do this self-service process. A week later my name was updated online; customer support said I'd be receiving a new physical insurance card in the mail shortly.
Changing your name with the FCC
I have an amateur radio license, so I needed to do this. You probably don't.
I submitted an Administrative Update application in ULS online filing. Make sure to include a copy of the court order as a "Confidentiality" attachment. It will not be made publicly available if "Confidentiality" is the selected attachment type in ULS.
Changing your name with USPS
I have a PO box; I had to visit the post office where I receive mail in person and speak with a clerk. They handwrote corrections on my original Form 1093 after seeing my court order and drivers' license.