Assuming that the VPC is ready and there is one public subnet and one private subnet.
Just add an instance (I used Amazon Linux) in public subnet and all incoming/outgoing traffic. It is important to disable source/destination check on that instance (right click on the EC2 instance and you will see it).
Next you need to SSH into the NAT server and run the following commands:
sudo sysctl -q -w net.ipv4.ip_forward=1 net.ipv4.conf.eth0.send_redirects=0 sudo iptables -t nat -A POSTROUTING -o eth0 -s 10.0.0.0/16 -j MASQUERADE
And then test it they are all set:
sudo iptables -n -t nat -L POSTROUTING sysctl net.ipv4.ip_forward sysctl net.ipv4.conf.eth0.send_redirects
In the end, go back to AWS console. Go to VPC service and select the route table that is associated with the private network. Then change the default route (0.0.0.0/0) to the NAT instance.
Now you are good to go! All instances in your private subnet have internet access now.