Camoron,
Well, there are a few guides on setting it up, but since I don't know the version of Exchange that you are attaching to then I can't direct you to the right solution. So here is what we will do. Look for this document and follow it for setting up the gateway and preparing for UM.
(609028361) UVM E-Mail Synchronization Administrator Guide
Now, anytime that you see Office 365 that would be the same as Exchange since they are the same product line. There is also a KB that is labeled as "Setting up Exchange 2013 to work with the Mitel 5000 for Unified Messaging" which should also help.
Hopefully that points you in the right direction, but if you need to learn how to troubleshoot it better there are other things that you can do as well.
Thanks,
TE