Depends what your budget is etc.

We used Webmarshal at one of my jobs, wasnt cheap but good for handling students accessing dodgy sites :)

Could pull up all sorts of reports etc.

Doing this at the firewall level is the best long term solution, IMHO.

http://www.nirsoft.net/utils/browsing_history_view.html is one way to suck browser history out (if it has not been cleared) and have a scan through it, especially if this can be done on a domain-based network from a Windows server.  Not pretty, but I've seen it used to terminate an employee without actually touching their computer.

What is on the edge of the network? Any kind of firewall?