When a private server sends a packet to an external address, the route table sends it to the NAT gateway instead of straight to the internet. The gateway swaps the private source IP and port for its own public IP and a port it picks, and it records that mapping in a translation table.
When the reply comes back to the gateway's public IP on that port, the gateway looks up the table, rewrites the destination back to the original private IP and port, and forwards it inside. This is often called PAT, port address translation, because many private hosts share one public IP distinguished only by port number. A single public IP supports tens of thousands of simultaneous connections this way.
On AWS the NAT gateway lives in a public subnet, holds an Elastic IP, and the private subnet's route table points 0.0.0.0/0 at it. The public subnet in turn routes to an internet gateway. The flow is private host to NAT gateway to internet gateway to internet, and back the same way.