Once Network Address Translation is in place, the next service that is almost universally needed is name-to-address translation, commonly provided by DNS, the Domain Name System.
For the boundary machine itself, this is not a problem, since it has one foot in the public network already. Therefore, a common way to set up such a machine is to configure it with a cacheing name server; a named daemon is set up initially so that it knows only a very few name-IP address mappings, but as it resolves others, it remembers them for future requests. The details can be found here.
Systems on the Private Network, however, face two choices: they can make DNS requests directly to the upstream nameservers (usually at the ISP that supplies the Internet connection), or they can take advantage of the cache on the boundary machine.
This second arrangement has two advantages: first, results come back faster (if the cache has the mapping), and second, the traffic back and forth on the ISP link is reduced (possibly quite a bit, if there are several systems behind the firewall). For these reasons, it is usually a good idea to use the second approach for a private network with more than a few machines attached to it. The correct way to do this is to configure a named on the boundary machine to listen to both loopback and internal network addresses, and then to configure each private-side system behind the boundary machine so that it sends DNS requests to the boundary-machine private-side address. The named will forward any request that it cannot resolve on its own.
This is done on Linux machines by editing the nameserver line in /etc/resolv.conf on each private-side system, giving the address of the private-side interface on the boundary machine (probably 192.168.1.1 or something like it), and specifying that the boundary machine itself use the nameserver at IP address 127.0.0.1.
On Windoze machines, the IP address of the private-side interface on the
boundary machine should be inserted in the list found at
Settings\Network\TCP/IP\Properties\DNS Configuration\DNS Search Order.