If you are running a recent 2.6 Linux Kernel this four step process should work for you. This has been specifically tested on FCore 3, 4, 5, and 6.. should work on any modern Linux distribution. All of these commands must be executed as the root user.
First you need to tell your kernel that you want to allow IP forwarding.
echo 1 > /proc/sys/net/ipv4/ip_forward
Then you'll need to configure iptables to forward the packets from your internal network, on /dev/eth1, to your external network on /dev/eth0. You do this will the following commands:
/sbin/iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE
/sbin/iptables -A FORWARD -i eth0 -o eth1 -m state --state RELATED,ESTABLISHED -j ACCEPT
/sbin/iptables -A FORWARD -i eth1 -o eth0 -j ACCEPT
You should now be NATing. You can test this by pinging an external address from one of your internal hosts. The last step is to ensure that this setup survives over a reboot. Obviously you should only do these last two steps if your test is a success.
You will need to edit /etc/sysctl.conf and change the line that says net.ipv4.ip_forward = 0 to net.ipv4.ip_forward = 1. This essentially tells your kernel to do step one on boot.
Ok last step for Fedora/RHEL users. In order for your system to save the iptables rules we setup in step two you have to configure iptables correctly. You will need to edit /etc/sysconfig/iptables-config and make sure IPTABLES_MODULES_UNLOAD, IPTABLES_SAVE_ON_STOP, and IPTABLES_SAVE_ON_RESTART are all set to 'yes'.For non-Fedora/RHEL users you can simply setup an init script for this or simply append these commands to the existing rc.local script so they are executed on boot