OK. I personally recommend running the linux machine as the gateway. It's more secure. However windows is easier to set up. That's not to say linux is hard, you just have to know what's going on. Things to expect/problems to anticipate:
*Make sure you have an ethernet card that is supported. Do a
www.google.com/linux search.
*Have a look at the IP Masquerading HOWTO on
www.tldp.org. It will show you step-by-step how to network the two computers together and share an internet connection.
That's about all I can think of off the top of my head. If you have any questions I'll be happy to answer them for you.
I would have posted this last night but the site wouldn't let me.