Squid: complex beast of a proxy software that can do transparent / intercept proxying. I'm going to assume you're using this already.
Polipo: great proxy program, but author opposes transparent / intercept proxying on technical and political grounds.
* Install polipo
* Configure polipo: "allowedClients" should have 127.0.0.1 & your local subnet; uncomment "diskCacheRoot = """; uncomment "dnsQueryIPv6 = no" (edited 2-2-2010: treat cache as shared & only resolve IPv4 addresses, since you can't transparent-proxy IPv6)
* Add "cache_peer localhost parent 8123 0 no-query no-digest" to the squid.conf file.
You may need to tweak Polipo & Squid still regarding memory sizes and cache performance, but with Polipo as a memory-only prefetcher, you should find your caching performance to be much improved.
Reference on parent proxies in Squid