From the Outlook 2016 help page:

Focused Inbox was first released on Outlook for iOS and Android. All versions of Outlook that receive updates will soon become Focused Inbox capable, including Outlook 2016 for Windows, Outlook 2016 for Mac, Outlook on the web, and Mail for Windows 10. You'll see Focused Inbox once your Office 365 or Outlook.com mailbox is enabled for it.

It sounds like they will enable it when they update Outlook 2016 to be compatible. If you read here, it sounds like it started rolling out to Office 365 customers in early September. I do not have it enabled on my version yet either.

Update November 2017

Microsoft has made changes to Office 365 so this answer may no longer be relevant. In fact, the changes should fix the problem described in the question:

Organizations with modern authentication have already been getting Focused Inbox. We made changes to Outlook which allow organizations with basic authentication to begin getting Focused Inbox

Note that you may still have to switch your update channel for Office 365 to get the newest version of Outlook.

These changes will be available with build 16.0.8730 Version 1711 and greater.

(The quoted announcement is only available to Office 365 administrators so I am not providing a link here.)

Original answer

Root Cause

For Focused Inbox to work with Outlook 2016 you have to enable Modern Authentication in Exchange Online. As a nice side effect of enabling this feature Outlook 2016 will be able to connect to Office 365 Exchange Online when you have multi-factor authentication enabled without using an application password.

Microsoft claims that this setting is enabled by default. This is probably true for new customers but I had to turn this setting on manually on my Exchange Online organization that probably was created before this feature was available.

Using PowerShell

To turn on Modern Authentication you have to connect to Exchange Online using PowerShell. As I am using multi-factor authentication it was not immediately obvious how to do that but it is described in Connect to Exchange Online PowerShell using multi-factor authentication which I expect to work even if you do not use multi-factor authentication. Briefly,

1. Go to Office 365 Admin center on the web
2. Expand the Admin centers menu on the bottom left and select Exchange
3. In the new browser window/tab that opens select hybrid in the menu on the left
4. Select the Configure button labeled The Exchange Online PowerShell Module supports multi-factor authentication. Download the module to manage Exchange Online more securely.
5. Accept the prompt to open the click-once appliction

6. In the PowerShell terminal window that opens execute the following command:

   Connect-EXOPSSession -UserPrincipalName <email address used to sign in to Office 365>
   

7. Sign in to Office 365 in the dialog box that opens and wait for the PowerShell command to complete execution

You are now able to configure your Exchange Online organization using PowerShell commands in the PowerShell terminal window.

Configuring Modern Authentication

You can inspect the configuration of your organization using Get-OrganizationConfig. To inspect the Modern Authentication setting execute the following command:

Get-OrganizationConfig | Format-List -Property OAuth2ClientProfileEnabled

To turn this setting on execute the following command:

Set-OrganizationConfig -OAuth2ClientProfileEnabled $true

Configuring Focused Inbox

The Focused Inbox feature can be controlled both on the organization level and the mailbox level. To inspect the setting a the organizational level execute the following command:

Get-OrganizationConfig | Format-List -Property 'Focused*'

and to turn it on at the organizational level execute

Set-OrganizationConfig -FocusedInboxOn $true

To inspect the setting for a mailbox execute the following command:

Get-FocusedInbox -Identity <email address>

and to turn it on at the mailbox level execute

Set-FocusedInbox -Identity <email address> -FocusedInboxOn $true

This setting can also be configured by the mailbox user in Outlook Web Access.

Both settings have a timestamp and the most recent setting is the effective setting according to Microsoft. So if a user turns off Focused Inbox and Focused Inbox is then turned on at the organization level the user will have to turn Focused Inbox off again.

If you have never configured Focused Inbox you will most likely see that both the organization and the mailbox setting is neither true nor false. It is simply missing. My guess is that this might lead to the strange behavior where Focused Inbox is randomly turned on and off without user interference. It is hard to test so I might be wrong.

However, my suggestion is to take control over the setting and set it either to true or false on the organization and/or your mailbox depending on your preferences.

Summary

1. Turn Modern Authentication on
2. Make sure that Focused Inbox is enabled
3. Make sure that you have the latest version of Outlook 2016 (the monthly channel)

When I did this I had to do one final step for Focused Inbox to appear in Outlook and that was to reconnect to my Office 365 mailbox in Outlook. If you have a simple setup where Outlook only connects to Office 365 I find that the easiest way to do this is to delete my MAPI profile and when prompted by Outlook create a new one. Then you avoid the issue where Outlook will not delete your Office 365 account.

If you have a more complicated setup with multiple email accounts, multiple email profiles and/or local data files you should be very careful before you follow this procedure.

1. Close Outlook 2016
2. Search for mail in Control Panel
3. Open the Mail (Microsoft Outlook 2016) (32-bit) control panel applet
4. Select the Show Profiles button
5. Select Remove to delete the single profile (most likely named Outlook)
6. Start Outlook 2016 and when prompted for a profile name provide Outlook
7. Configure the new profile to connect to Office 365

Now Focused Inbox should appear in Outlook 2016.