When going to describe this page, I was given a great haiku:
Windows NT crashed. I am the Blue Screen of Death. No-one hears your screams.
A perfect introduction to the science of creating a LinuxRouterBox!
Connects to the Internet (via ADSL, dial-up, etc), provides NAT and 'masquerading' of the connection to any number of computers on your network. Provides a FireWall. Allows you to provide a local MailServer, a WebServer, DynamicDNS, WebProxy any of the useful things you might want to do with any server machine.
I quote my parents as a great example; they have a computer, my brother has a computer, and they were all discussing getting ADSL. The parents wanted control of the connection, my brother wanted to be able to use the DSL without their computer being on, and I wanted them not to buy a Windows-only modem :)
Otherwise, you might just want to learn about Linux, or be able to ensure the connection at your house will still be up when your main PC has gone to a LAN, or crashed, or is turned off at night, or whatever myriad of other reasons you might have.
This introduction is written with the relatively new Linux user in mind. It is written for DebianLinux because of the ease of installing software. This task is perhaps easier to provide under another distribution (see SelectingADistribution for a bit of background) -- if you can figure all this out, you can change distribution.
This section is being left terse at the moment; make sure to read PartitioningSuggestions. When you're finished this stage you should have a basic Linux installation.
See AptSourcesList for information about what this file is and what you might want to put in it.
When this is done, perform
apt-get update
This will bring your database up to date.
Ensure you have iptables installed;
apt-get install iptables
The default kernel from your distribution may not be set up for firewalling. You will need at the very least iptables support: ("Networking Options" -> "Network packet filtering" and then "IP: Netfilter Configuration" -> "IP tables support" a bit further down).
Enabling the "Socket Filtering" support is probably also a good idea (in case you want to DHCP from the machine, although maybe dhcp-server doesn't require this).
See PerrysFirewallingScript for instructions on how to do this
See ThingsToDoWithYourLinuxBox for some background info.
Install BIND. You can name your internal network easily enough. See NamedNotes. Setup hosts for "smtp", "wpad", "proxy" for your various services. Thusly if you move the smtp server to another machine, a simple DNS change will update all the machines on your network.
Install a dhcpd(8)? server daemon to work as a dhcp server for the network.
To host various reporting services used below.
Install Squid. If you have a WebServer on the firewall, be sure to setup WPAD so the windows machines can configure themselves correctly. You may wish to transparently proxy people through your WebProxy. When configured with a program that can take Squid logs and provide reports about it (see SquidNotes). This can be used by parents to monitor their childrens activity on the Internet.
Install Exim or SendMail as a SMTP server for your local network. If you trust your ISP, configure it's smarthost to be your ISP's SMTP server. You should probably bind this to your internal interface only.
Install a SNMP server (bind it to your local interface only!) and use something like Cacti for graphing bandwidth usage.
Incomplete; being worked on.
Comment for the end - IPCop 
http://www.ipcop.org is a nice tidy linux firewall install, which deals with dial-on-demand or always-on connections. It runs better on a pentium machine, but 486 is fine too. IPCop sets up squid for web caching, a caching dns server, and standard stuff like an internal DHCP server.
One page links to LinuxRouterBox:
