Answering my own question in case it helps somebody.
As mentioned in comment by @SharePointer you need to register an app in Azure AD in order to authenticate against it. That app that you register needs to be given permissions to your SharePoint Online.
Login to Azure Portal at https://portal.azure.com that is used by your O365 Tenant where you want to access the SharePoint site.
Navigate to Azure AD. Find "App Registrations" in the menu. Select "New App Registration". Give it a name like SPO or POSTMAN. Select the Application Type to be "Web app / API" and the Sign-on URL to https://www.getpostman.com/oauth2/callback
Once it is registered note the Application ID and copy it to notepad.
Go to Required Permissions in the application you just registered. Select SharePoint Online under the Select an API in step 1. Then under 2 Select Permissions choose "Have full control of all site collections".
Now choose KEYS blade and add a key. The key only shows once when you save it. Copy it to notepad.
Go to POSTMAN app on your desktop. Create a new request. For example, https://mytenantname.sharepoint.com/sites/mysitecollection/_api/web/lists
Set a header of "Accept: application/json; odata=verbose"
Go to the Authorization tab in POSTMAN. Select Oauth 2.0 from the dropdown and press the Get New Access Token.
Fill out the fields in that dialog like below:
Auth URL : https://login.microsoftonline.com/common/oauth2/authorize?resource=https://mytenantname.sharepoint.com
Access Token URL : https://login.microsoftonline.com/common/oauth2/token
Client ID :
Client Secret :
Grant Type : Authorization Code
Click Request Token button.
At this point you should login with an admin user. You will also be asked to allow the permissions you set on the Application in Azure AD. This is why you need to log in as an Admin account. Accept the permissions request when asked.
The token is returned. Copy it to notepad and then click the "Use Token" button. This fills in the token to the correct place in POSTMAN.
Now Send your request and you should have a successful returend JSON list of lists.
In addition to above I have found that I need to create a certificate in order to authenticate. Just registering the app and giving permissions was not enough.
To do this check out the makecert command in a Visual Studio Developer command prompt. Example below:
makecert -r -pe -n "CN=POSTMAN-TEST" -b 12/15/2014 -e 12/15/2016 -ss POSTMAN-TEST -len 2048
Then go to mmc.exe and the Personal folder in the Certificates snap in. Export the cert you created with the command above to a .CER file. Then go to Azure Portal and your registered app that you did above. Download the manifest file. Replace the section for the key credentials in the manifest file and upload it back to the app registration in Azure.
For example put your values from your CER file into this section: