You might be able to keep a cache of pages accessed, indexed by the IP of the requester. (If your proxy is on an intranet, this could work. If it's on the Internet, that'll likely screw things up, as IPs can be non-unique due to NAT, firewalls, or other proxies.)

If a request comes in with a relative link, just prepend the last accessed request.

That doesn't seem very robust, and it requires an idealistic situation where you can guarantee that IPs are unique to individual machines. If so, good luck.

Updated: My esteemed colleague spudzeppelin implies one other thing -- with a web-based proxy, you'd have to scan *everything* in the datastream that might possibly be a link, and prepend your URL. That way lies madness.