One headache that I ran into early on with Microsoft Office 365
(hosted Exchange, SharePoint and Lync) is that your Lync client is completely empty when you start deploying your software. I assumed it would automatically pull in all of your Office 365 user accounts and pre-populate them as contacts. No such luck.
Also there doesn't seem to be any sort of "import" feature in Lync where you could pull in contacts from an Excel sheet or Outlook list. So that leaves you having to manually add all of your employees as contacts on each Lync workstation. No thank you!
So what I typically do is create a distribution list or two in the Office 365 portal. Then you can just add that whole group to Lync all at once.
So first, login to your Office 365 portal with an admin account. Under the "Exchange" section, click on "Manage". Then go to the "Distribution Groups" tab. Now click on "New..". Now you can give your group a name (such as "Office Staff", "Sales", "Service", "All Users", etc.). Then scroll down to the Membership area and hit "+ Add..." to begin adding your Office 365 users to this group. When you are finished, hit "Save". You'll now see your new distribution group listed on this page.
You may not be able to add this group to Lync immediately. It could take a few hours for everything to update in the cloud. But after some time has passed, you'll be able to go into your Lync client and in the "Find a contact" field, enter in the name of your distribution group ("Office Staff, Sales, etc."). Once it finds the group, you can just hit the "+" symbol or right-click and "Add to Contacts". Once the group shows up in Lync, you simply hit the little triangle indicator next to the group name to expand it and show you all of the individual members of that group. So now you only need to add one or two groups on each Lync client that you install, rather than manually adding every user.
One awesome perk of using this method is that now you can control and update the contact lists from a central location. If you get a new employee or if someone leaves, you just go back into your distribution group settings and make the changes and just wait for them to propagate out to the clients. You don't need to have the users manually adding or deleting contacts.