Squid Proxy Server would be one good free way.

You could also do redirects by changing their local HOSTS file to redirect to your own internal Website that gives them a warning message about not using such sites during work.