Для настройки NAT используем сетевой экран iptables (см. http://informatic.org.ua/forum/73-746-1 ).
Настройка.
Пусть eth0 - это интерфейс интернета, eth1 - интерфейс локальной сети.
Сначала нужно разрешить маршрутизацию в ядре Linux командой:
echo 1 > /proc/sys/net/ipv4/ip_forward
(в файл ip_forward записывается параметр 1 вместо 0)

Затем нужно:
1) разрешить пересылку пакетов с интерфейса на интерфейс. Я добавил следующие строки:
iptables -t filter -I FORWARD -o eth1 -i eth0 -j ACCEPT
iptables -t filter -I FORWARD -o eth0 -i eth1 -j ACCEPT
(-о ethN можно опустить)

2) разрешить пересылку пакетов с трансляцией адресов:
iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE

Вместо действия MASQUERADE можно использовать SNAT.
SNAT работает аналогично MASQUERADE, однако позволяет указать адрес «внешнего» интерфейса (опция --to-source), например, если на внешнем интерфейсе шлюза «висит» несколько статических адресов, например, 208.77.188.166, 208.77.188.167 и 208.77.188.168, можно использовать балансировку между этими адресами:
iptables -t nat -A POSTROUTING -o eth0 -j SNAT --to-source 208.77.188.166-208.77.188.168

3) сохранить правила (иначе при перезагрузке ПК или файервола выполненные настройки удалятся):
iptables-save

На хостах локальной сети нужно указать IP шлюза (внутреннего интерфейса eth1 маршрутизатора) - можно прописать командой route или в свойствах интерфейса.
Если в локальной сети есть win машины дополнительно нужно настроить samba.
Все, Linux готов для работы в качестве маршрутизатора.

Для маршрутизаторов можно использовать специальные дистрибутивы на основе Linux: SmoothWall (бесплатное), MikroTik (платное) и т.п. Их удобно устанавливать на устаревших ПК, с широкими возможностями дистанционного управления.
Возможно что-то упустил или допустил неточность - пишите.

Ссылки.
http://ru.wikipedia.org/wiki/Iptables
http://ru.wikipedia.org/wiki/NAT