As I understand it, a public subnet is one that can route traffic to the internet via an Internet Gateway, and a private subnet is one that cannot (can't reach the internet nor it can be reached from it). In order to reach the internet, a private subnet needs to route traffic through a NAT Gateway.
I can confirm this because I am actually using this setup successfully.
But... the Amazon docs say otherwise (bold emphasis is mine):
The instances in the public subnet can receive inbound traffic directly from the Internet, whereas the instances in the private subnet can't. The instances in the public subnet can send outbound traffic directly to the Internet, whereas the instances in the private subnet can't. Instead, the instances in the private subnet can access the Internet by using a network address translation (NAT) instance that you launch into the public subnet.
Does it matter where the NAT gateway resides? If it does, what are the use cases of putting it in a private/public subnet?