Access Company Directory on Samsung S3
Assuming you already have the Exchange account added on your phone, if you go to Contacts, and search for a name, it should bring up directory results. Make sure you hit the search or enter button on the keyboard.