We did Aktau-Nukus last week.
First, on the KZ railways website (bilet.railways.kz), we booked Aktau (MANGISTAU, МАНГИСТАУ) to Beineu (BEINEU, ВЕЙНЕУ), leaving at 8.10am and arriving at around 3pm.
The UZ railways (railway.uz) showed there was a connection to Nukus on the same day (late evening), but we couldn't book it online (buggy checkout). We went anyway and figured we'd buy the ticket at the Beineu station.
The Aktau-Beineu leg was easy. We took a Yandex taxi from Aktau to the station (in the nearby town of Mangistau), it took under 30 minutes and cost 2590 KZT (5-6 USD). The train was great, there was a lot of space in our car but others were packed. It's a sleeper so napping is an option. Passengers were each given a paper cup with a teabag and instant coffee, and the food in the (very cool) restaurant car was good.
We arrived in Beineu about 30min after schedule (maybe don't plan a short connection). At the ticket office (no English spoken) we learned that THERE WAS NO EVENING TRAIN and as far as we could tell from the paper timetables at the station, the only Beineu-Nukus train leaves every other day at 4.11am. So we had to spend two nights in Beineu until the next train (hotel Zhizhek is pretty nice, 10000 KZT (22 USD) for a twin room, didn't find anything cheaper.
https://maps.app.goo.gl/F4mY3tEzfjoSL1i87)
The Beineu-Nukus train leaves at 4.11am local time, even though your ticket says 5.11am (it's railway administration time). As previous reports have said, get to the station 1h early, border control will probably already be in progress on board the train. About 2h after departure we got to the UZ border, locals stay on the train and we had to go to a little room for a quick interview (where are you from where are you going etc). All in all the two borders take some time but we had no problems at all. The train was much older than the previous one, there were cups and teapots available but we had to use our own teabags. We didn't see whether there was a restaurant car, but ladies go up and down the train all day selling food and drinks. Try the manti. (We had no UZS but one of the ladies changed our remaining KZT at a very good rate).
In Nukus the station is a bit far from the center. Taxis wanted 30k UZS. We got a ride for 15k. If you have a SIM card, Yandex is the cheapest. Nukus was actually much nicer than we thought and we stayed 3 nights (great koryo-saram food), don't rush to Khiva!
---
If we had to do it again:
- check when the next 4.11am Beineu-Nukus train leaves on UZ railways
- get an Aktau-Beineu ticket with KZ railways for the day before
- catch some sleep at a hotel in Beineu, it's hard to sleep before 7am on the Beineu-Nukus because of the border checks)
- go to the Beineu station about 1h early (3am)
- carry snacks and tea bags