Add New Users using Exchange Admin Center (Exchange 2016)

This only applies to new Active Directory users.  To look at how to use SMTP matching to link an on-prem user to an existing O365 mailbox in a hybrid environment follow this guide.
1. Log into the Exchange Admin Center: https://mail.contoso.com/ecp
2. In the EAC console of your on-premises hybrid server, go to Recipients > Mailboxes and click on the plus sign above the “Display Name” column and choose “Office 365 mailbox.”

3. Complete all the fields as required and click save. You can edit the user’s mailbox properties afterwards to add information such as title, manager, address and phone number if you wish.  Exchange will automatically create the AD account for you.

4. Sync using AD Connect. 
You can either wait for the next sync cycle or force it.  The user will appear in Office 365 and an Exchange Online mailbox will be provisioned not long afterwards. Once everything is synced you can add a license.
5. License the User.
1. Go to https://portal.office.com
2. Select the Admin tile
3. Go to Users and choose Active users

4. Select the user in question, go to the Product Licenses field and click Edit
5. Choose a location then click the slider to activate an available license
At the bottom of the Product licenses pane, choose Save