In anutshell you want to do:
# In the NAT table (-t nat), Append a rule (-A) after routing
# (POSTROUTING) for all packets going out eth0 (-o eth0) which says to
# MASQUERADE the connection (-j MASQUERADE).
iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE
# Turn on IP forwarding
echo 1 > /proc/sys/net/ipv4/ip_forward
Lets call the box running iptables "router". You would set the default gateway on your other machines to point at router. Their DNS could point to an external box, or your internal machine.
(Above examples assumes eth0 is your internet interface).
See
http://netfilter.samba.org for lots of docs on how to use iptables.
Setup BIND (ugh...lots of security problems) or djbdns (
http://cr.yp.to) on your internal box to do DNS (most likely a caching server which points at the external world).