Without my Websense hat on (as I deal with the Software as a Service, as opposed to on-premise) but as I understand it, if you drop in a squid proxy (pretty easy to do) and if it can drop in as the gateway for these boxes, a few iptables rules to redirect port 80 traffic, or alternatively set the group policy for proxying through the squid box, it should be relatively simple.
I'm not sure how it differentiates on the users though
