We probably need more info. Otherwise, you're in the "I installed and tried everything but it doesn't work. Help." catagory.
Are you talking about MSN Messenger, the popular instant messaging buddy tracker program? Or do you mean the messenger service in the event manager, which allows pop-up messages to be sent between Windows PCs on a LAN? (I will assume you mean MSN messenger for now...)
What's the workstation OS? 95, 2000... When you attempt to install Messenger as the user who will be using it, what errors do you get? Is this a corporate environment where there may be group policies in place?
"Giving permissions" usually means 2 things when talking about making applications run. File permissions (granted with explorer) and Registry Permissions (granted with regedit). MSN Messenger is a pretty clean app in this reguard. You install it as a "Power User" or "Administrator", and then "Users" can run it.