Proxies
Internet sharing through a proxy isn't as transparent as NAT routing. With proxy software, the proxy server maintains a session with the Internet, and systems on the private network have sessions with the proxy server. The proxy server acts as the HTTP/FTP/Mail/Telnet/SOCKS/etc. server for all the computers on the private network. Proxy servers generally need more configuration work than NATs, and fewer applications work as well with proxy servers.
In terms of pure functionality, proxies are inferior to NATs, but the explicit separation between client and Internet machines provides proxy servers with security, administrative abilities, and caching services that NATs lack. A proxy server can save clients time by caching previously downloaded pages for local network access. Proxies also give administrators control over what, how, when, and to what extent or degree clients can access the Internet. People with "net-god" complexes might find the power of proxy server administration intoxicating.
Here at Firingsquad we've been playing around with WinProxy and NAT32, two of the more common Internet sharing programs out there.