I am going to asume you have already installed Linux..

Open up any text editor and put this in /etc/rc.d/rc.local

#Turn on IP forwarding

echo 1 > /proc/sys/net/ipv4/ip_forward
/sbin/ipchains -P forward DENY
/sbin/ipchains -A forward -s 10.0.0.0/255.255.255.0 -j MASQ

#If you telnet a lot, this will stop your connections from timing out at inconvenient times. 
/sbin/ipchains -M -S 7200 10 60
#
#Uncomment the next line if you are using dialup or do not have a static ip.
#echo "1" > /proc/sys/net/ipv4/ip_dynaddr
#
#Uncomment these for special services.
/sbin/insmod ip_masq_ftp
/sbin/insmod ip_masq_irc
/sbin/insmod ip_masq_raudio
/sbin/insmod ip_masq_quake
#/sbin/insmod ip_masq_cuseeme
#/sbin/insmod ip_masq_vdolive

put this in /etc/rc.d/init.d/network or you can put it in /etc/rc.d/rc.local

# Setup Automatic IP spoof protector
if [ -e /proc/sys/net/ipv4/conf/all/rp_filter ]; then
echo -n "Setting up IP spoofing protection..."
for f in /proc/sys/net/ipv4/conf/*/rp_filter; do
echo 1 > $f
done
echo "done."
else
echo PROBLEMS SETTING UP IP SPOOFING PROTECTION. BE WORRIED.
echo "CONTROL-D will exit from this shell and continue system start up."
echo
# Start a single user shell on the console
/sbin/sulogin $CONSOLE  
fi

You will need 2 nics for your gateway. The first nic (eth0) will be connected to the internet. The second (eth1) will be on your local intranet. Make eth1 have the IP address of 10.0.0.2 and a netmask of 255.255.255.0. Make the other machines on your local net have the ip address of 10.0.0.[3-254] and a netmask of 255.255.255.0. Once that has been done and all the machines are connected, they should be able to "talk" to each other.

Now you need to set the machines on the local net to forward packets to the gateway when they want to use an ip address not within the local net. To do that you will need to add the gateway's IP address in the gateway tab for windows, for a linux box type "route add default gw " also don't forget to add the ip address to your isp's dns server in the dns tab for windows and "/etc/resolv.conf" for linux/unix.