do I install the plug in on each of their workstations?
Yes. Any Method user in your company should have the Outlook plug-in installed on their workstation.
We are using Exchange. Does that present other issues?
No - you should be able to install and use the plug-in with no problems.