I have one private subnet and one public subnet in one availability zone, and the same two subnets in another zone.
Can I create one NAT gateway in one public subnet, and create two route tables for the two private subnets, which both point to this single NAT gateway?
Or do I have to create two NAT gateways, one for each AZ?
Yes, you can have one NAT gateway. But for high availability it's better to have one NAT gateway per AZ.
The docs clarify this:
If you have resources in multiple Availability Zones and they share one NAT gateway, in the event that the NAT gateway’s Availability Zone is down, resources in the other Availability Zones lose internet access.