I use a firewall builder program called shorewall quite succesfully, it makes it fairly easy to setup a Dynamic Network Address Traslation configuration on your box. I personally use debian stable, but I can't recommend it unless you have a week of free time on your hands lol. As far as I know mandrake includes shorewall from the word go, so check it out!
for docs goto www.shorewall.net,
i'd be happy to share my shorewall configuration files over email, their not great up they work well enough my 5 pc network, eg KaZaa and games through the server.