i don't really know much about large scale networks... sorry, i'm only a student... but I would have thought that you migtn't actaully need a proxy if you are simply trying to get internet access on a number of machines, as you can do that at a much lower level, using just IP masquarading and port forwarding, whcih generally takes very little setting up and such. all you then simply need to do is to set each machines gateway to be the net connected machine, which then passes data through it transparently. I do this with a simple app called 'firestarter' which runs in gnome and enables ip forwarding and such like just by selecting a button. I'm not aware of how this scales up on a large network though. You can do a similar sort fo thing under windows using winroute.
if you do actaully want to use a proxy w/ caching and such like, then i guess you want to look at the squid howto, but to be honest i've never used squid as i've never needed to, and know next to nothign about the benefits of proxy other than having more control over ports and such.