linux is perfect for what you want to do:
first of all, you are correct in that you need 2 NICs for the linux box. One nick will be for the external network (the internet)... it will probably be assigned a dynamic ip via dhcp. The second NIC is for your internal network: this one you assign a private ip address, say 192.168.0.1 (most common private ip)... your other machines should be .2, .3, etc.
on the software end of things, you will have to setup ip masq on the linux box, to route between your private, internal net, and the public internet. Make sure you are using an up to date linux distro, like redhat 6.1, so that the kernel is at least 2.2.12.. (using ip chains). Lastly you NEED to read the IP MASQUERADE HOWTO... its essential.. also read the trinityOS setup - an essential guide to linux security... he has a perfect example of what you want to do.