After installing the OneNote 2016 PC client it asks you to sign in to the cloud.
If it decides that you have to use a business account (i.e. you are trying to set it up on a PC that is a part of a domain), but you need to use your personal account it is going to complain. It will either say that your email address’ domain isn’t known, your account does not exist/not found or it doesn’t look like work or school e-mail.

The following registry change will make it accept a personal account. First exit OneNote app, then change the value in the HKEY_CURRENT_USER\Software\Microsoft\Office\16.0\OneNote\FirstBootStatus key to hexadecimal 2000202.