Sólo tres simples pasos que podrás añadir a algún script en el inicio de tu sistema:

    modprobe iptables_nat

    iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE

    echo 1 > /proc/sys/net/ipv4/ip_forward

Sólo debes cambiar eth0 por el dispositivo que está dando salida a internet (ppp0 para modem normal, eth1 por si tienes una tarjeta inalámbrica en ese dispositivo, ...)

Suerte y a disfrutarlo. Al menos a mí me ha funcionado. Ya sabes, si quieres más informacin, man aplicacion :-DP.D. Está basado en iptables y kernel de la serie 2.4 en adelante.