You need some sort of software to do the NAT and routing stuff on the linux box. I'm using Mandrake 8.1 here and in the setup when you install there is the option to set up as a server of any kind including a NAT, you can also do it in the RPM installer provided with the OS.
I'm sure redhat has something similar.
