Since NAT gateway only have redundancy within a single AZ, if I want to have a public/private pair of subnets in every AZ for the purpose of multi-AZ redundancy, I should have a NAT gateway in every AZ, shouldn't I?
Otherwise, if I have only one NAT, if the AZ goes down, all the subnets in all AZs go down with it, thus defeating the purpose of this multi-AZ deployment.
Am I right or wrong?
Yes, ideally you would have one NAT gateway per Availability Zone (AZ).
AWS documents this advice at Comparison of NAT Instances and NAT Gateways:
Highly available: NAT gateways in each Availability Zone are implemented with redundancy. Create a NAT gateway in each Availability Zone to ensure zone-independent architecture.
A single NAT gateway in a single AZ has redundancy within that AZ only, so if there were zonal issues then instances in other AZs would have no route to the internet.
Note: there are per hour charges for each NAT gateway as well as per GB data processed (see VPC Pricing). See How can I reduce data transfer charges for my NAT gateway?