okay - as i understand your post you wish to have your MS Windows XP box be a gateway for the Linux box. I thought MS Windows had some thing like internet connection sharing, while i have no MS Windows here i can not really say how to have Linux see the MS Windows box as a gateway...
i think this will help ->
http://www.homenethelp.com/ics/ics-install-sxp.asp i would use the Macintosh instructions and modify for Linux.
but of course i would use Linux as the gateway for all of them