I think you will need to use the server as proxy for all your users, and configure the policies on there. Software such as WebSense can configure this type of policy, but is quite expensive. Other people on here may know of cheaper alternatives.
You will also need to configure your firewall, or Internet router, to prevent anyone bypassing the proxy. Otherwise they will just access the Internet as they do now.
You could also configure these policies on the firewall or router, if it supports this type of filter.
But the best way is to configure Firewall cause it prevents any by-passer on your server.