What firewall do you have? Some firewalls have the ability to filter whether it's built in or added as an addin module (which can either be hardware or software).
At a previous employer (who at first didn't see the value in monitoring traffic other than watching the bandwidth) I used a log analyzer to at least see what sites were being hit the most and then I'd take that data and make a simple set of charts in Excel to show to management (management likes pictures :) ).
I gathered data over a 60 day period and, at that time, World of Warcraft was the most popular site next to MySpace and Facebook. I also showed Bit torrent traffic which I had to tell management that this could be anything from streaming media to possible illegal downloading of copyright media.
That was enough for management to give me the approval to seek out a content filtering solution. It needed to be non-intrusive to the endusers and not have a negative impact on the Infrastructure.
My firewalls were Juniper Netscreen's which I was able to add content filtering that included virus scanning.
Then to further secure the infrastructure a dedicated SPAM/Virus filtering appliance was added along with a dedicated proxy type apppliance. Both were behind the firewall.
By spreading the load (so to speak) it helped reduce the load on the firewall.
I'm also a bit weird in that I really don't like to do much tweaking on the firewall. In other words once I have the firewall set I really don't like to tweak with it unless I'm adding a new route, NAT, etc.
For something like filtering where you will be monitoring it a lot and even doing a lot of tweaking, I'd rather break that appliance than the firewall. :)
All that said, I did enlist upper management to make the annoucement that tighter controls were going to be implemented and what the reasons were. Management also reminded the users about the acceptable useage pollicy that everyone had signed upon the first day of eimployment.
Sorry for the long response.
What I would do in your case is to try and generate some sort of reports from your firewall, router or even switch which shows the outbound traffic.
Then analyze where most of the traffic is going including how many inappropriate sites are being visited and how often. Remember, sometimes people are redirected to a porn site on accident either by a mistyped URL or by a page redirection so you need to trend that activitiy.
Once you're got enough data present that to managment to make them aware and ask how do they want you to address it. It may be as simple as them sending a mass e-mail to the company to asking you to put in a solution to help better control this activity; and by controlling you are also protecting your company so be sure they are aware of that too.
HTH.