4. Post-install Instructions

And it should all work now. Don't forget to:

Setup all the clients on the internal network to point to the Linux internal IP address as their gateway. (In windows right-click network neighbourhood->properties->gateway then change it to the Linux gateway internal ip.)
Setup all the clients to use your ISP's HTTP proxy if they have one, use a transparent proxy (WARNING - I've heard reports of transparent proxying to be very slow on very big networks), or run squid on your new linux gateway. (This is optional, but preferrable for large networks)
Be sure to specify a DNS when setting up your clients. Otherwise you will get errors on the clients saying 'cannot resolve address' etc. If DNS used to work (URL address worked) but doesn't after you setup Masquerading, this is because your ISP's/network's DHCP server can no longer tell you what the DNS address is.
[Offtopic] I wonder if you could simply send out a dhcp broadcast that just forwards on the dns server (and http_proxy while you're at it) without having to setup a dhcp server (or even if you do). Can someone mail me about this? :)
Thanks to Richard Atcheson for pointing this out.
Now you should start securing it! First turn off forwarding in general: "iptables -P FORWARD DROP", and then learn how to use iptables and /etc/hosts.allow and /etc/hosts.deny to secure your system. WARNING - Don't try this mentioned iptables rule until you have the masquerading working. You have to explicitely allow every packet through that you want if you are going to set the last rule to be DENY. (Undo with "iptables -P FORWARD ACCEPT")

Allow through any services you do want the internet to see.

For an example, to allow access to your web server do:

$> iptables -A INPUT --protocol tcp --dport 80 -j ACCEPT
$> iptables -A INPUT --protocol tcp --dport 443 -j ACCEPT

To allow ident (For connecting to irc etc) do

$> iptables -A INPUT --protocol tcp --dport 113 -j ACCEPT

To test it:

Try connecting from a client to the web using an IP. Google's IP is 216.239.33.100 (well that's one of them) and you should be able to get a reply from that. e.g. "ping 216.239.33.100" "lynx 216.239.33.100".
Try a full out connection by name. e.g. "ping google.com" "lynx google.com" or from Internet Explorer / netscape.

Where eth0 is the external Internet card, and 123.12.23.43 is the external ip of that machine.