How to use Salt Stack with minions all behind NAT (not publicly accessible, default salt ports not open)?

The answer is "it just works." There is no need to change the configuration files (of either master or minion). There is no need to worry about NAT or firewalls for the minions.

However, on the master, two ports need to be opened on the firewall. I accomplished this with:

iptables -A INPUT -m state --state new -m tcp -p tcp --dport 4505 -j ACCEPT
iptables -A INPUT -m state --state new -m tcp -p tcp --dport 4506 -j ACCEPT

On the minions, add an entry to /etc/hosts pointing the name "salt" to the master's IP address. Example:

root@minion2:~# cat /etc/hosts
127.0.0.1       localhost.localdomain   localhost
111.222.333.444  salt salt.example.com

Really, it is very simple.