I have win XP set up to ICS so I can access the net from the linux box.
I assigned the WinXP machine the static IP address 192.168.0.1 in the control panel > network connections > Local area network > TCP/IP > Properties. Obviously, enable ICS on the internet connection.
I assigned the address 192.168.0.2 to the linux machine,
entered the winXP address into the hosts section of the Network configuration dialogue on the linux box,
entered the winXP address (192.168.0.1) as the default gateway for the internet connection on the linux machine.
It's important to note that you can't use the Zonealarm firewall on the Windows machine if you want to use ICS. Can each machine ping the other?
I'm not on the linux machine at the moment, but if you have any problems I'll go rooting through the setup - I use FC3 but it shouldn't be that different to Mandrake I'd imagine.