Keep users from downloading from the net

How can I keep users from downloading programs from the internet? I have a 2000 server and 98 workstations with a few 2000 workstations. Trying to upgrade workstations slowly. Users will download things like messenger etc… that is not permitted. We need access to the net for our jobs – so how do we block some things that are not appropriate to download in a work place? Tried the education route, did not prove to be sucessful…Thanks