User service monitoring
We're doing exactly that here, with a server running a really basic HTTP server on a custom port on a separate thread that returns an XML status (nothing else, just that) - the client just uses a web request to get the XML before disassemble it and display it appropriately.
This approach also allows for future extensibility (verbose status, sending service control commands, adding a link to the XSLT file elsewhere for use with a regular web browser, etc.)
source to share
You can use WCF for this. Using WCF your service will open EndPoint which will provide status information to callers. Then you can create a tray icon app that can be deployed to employee workstations. The tray icon app can periodically poll the WCF service that hosts your Windows service and get status information. I know @Johan mentioned Remoting already and this is a similar approach. I would recommend WCF, though since the programming API is simpler IMHO and WCF will give you more flexibility about network transports, etc.
source to share
I guess your question is not how to actually do "traybar" -thing, but how to contact the service to get the information you want to show in the monitor / tray program?
This can be done in different ways, API is one way, using sendmessage / postmessage / getmessage is one way for 2 running programs to communicate with each other without having to store anything in files or databases.
DDE is another way. If it needs to be done over the network, then there is something called NetDDE, but I haven't done anything with NetDDE, I can't help anything.
But about API and DDE, feel free to ask more questions if you want to clarify.
source to share
I'll take the second question: is there a way to remotely install software on client machines?
Yes. However, this very much depends on your environment. For example, if you have an Active Directory domain, you can use Group Policy to push software installation to client boxes.
If you don't like it or you are not in the active directory, you can buy something like Altiris to push installs down.
Another option is to use login scripts that will run a custom program to determine if your program is installed and take appropriate action. But then you are probably better off buying Altiris.
source to share