In the new-style version of the website:

Step 1: find the "change" link next to your name and click it.
Step 2: you're dropped into a generic "Notification of change in personal details" flow. Click "Start now".
Step 3: select the "Change of name" checkbox. Click "Save and continue".
Step 4: For some reason, it now asks you about your address. Click "Yes" to "Is your current address in the UK?", and answer what your postcode is, and when you moved in. You must also provide a phone number. If you don't remember the day, month, and year you moved in, you cannot proceed. Come back later. Note that there is an entirely separate flow for updating your address that doesn't use this form. Press save and continue.
Step 5: It'll then ask your for your Unique Taxpayer Reference. Select "yes". Go back to the "Account home" section that you started this flow from and copy and paste the number, then press save and continue.
Step 6: Finally you are asked about the name correction. Click "No" to "Is this a correction of a previous name change" and provide a date for the name change. Select yes or no based on which of your first, middle, and last names are changing - note that this form does not tell you what the current data held is, so you just have to know what HMRC already thinks your name is. Pick whether this is just for contact purposes, or if this is a legal change of name. Click save and continue.
Step 6: Get a confirmation of what you've entered. Press "save and continue"
Step 7: Get a reference for the change of name