There are several server-based Internet Policing software products. Our company currently use SurfControl. This software "sniffs" all traffic and sends "fake" page to user if it sees request to prohibited site. It works virtually in any environment since it's not bounded to "firewall" or "proxy" server.
But for your scenario, since you are using Cisco PIX Firewall, I would recommend WebSence. This product is completely integrated with PIX software and PIX Firewall "authorizes" URLs against WebSence server (sure, it has internal cache to improve performance). It gives to you pretty good flexibility and works better than SurfControl.
Sure there are third variant, when you install caching proxy server and then install "web filtering" software over it. In this case you will gain "web cache" which, on practice, will save to you 15-20% of traffic, but not to many companies do that.
Good luck.