Depends on your network and where you are doing the blocking, and where the people who need to connect are.
If the users who need to get on an IM are all on specific computers (e.g. they aren't sharing a computer with users who you don't want on) I would simply deny all to the various ports that IM apps use (5190 for AIM as an example), give the users who need to have access a static IP and allow access for those specfic IPs.
Now there are issues with this, first if your users are intelligent they just change the port iChat uses to say port 80 and it will connect (in which case you can block access to the AIM server).
However, after that long explination, I'm assuming that isn't a possiblity for you, or you want to do it on the machine level. In which case I would recommend you look at Firewalk X. Haven't used it in awhile but I know it had the ability to only allow specific applications use the network with a lot of additional rules and features you might find interesting.