This used to be well documented in the NAM 5.0 docs, but now I see that it appears to be missing?  Only WSFED/WSTRUST is described.  I wonder why?  The steps in the NAM 4.5 docs are pretty much the same thing you want to do.  On the NAM side, you'll create a new Service Provider under SAML on the IdP and select "Office 365" as the Provider Type.  It has a pre-canned metadata setup for Office 365 already.  The other big piece you need to figure out is what you'll use for the Immutable ID.  I don't know what your user store is, but if it is AD, it's typically the AD object GUID or the mS-DS-ConsistencyGuid. But it all depends on how you are populating your M365 environment (Azure AD connect, eDir IdM driver, etc.).  You'll need to create an attribute set with that value and the email address and assign that to the service provider (I cannot recall, but I think you want the email address in the attribute statement, I'd have to look for sure).  Again, check the NAM 4.5 docs, it's in there.

You'll need to export the signing certificate you are using in NAM for the next part and have it in DER format. You'll need to use PowerShell for this part (I don't know if there is a way to do this in the M365 GUI). You'll need to use the MSONLINE PS module to do this (you can Google that and see how to set that up).  But here are the commands:

$dom = "yourdomain.com"
$url = "https://myidpurl.mydomain.com/nidp/saml2/sso"
$ecpUrl = "https://myidpurl.mydomain.com/nidp/saml2/soap"
$uri = "https://myidpurl.mydomain.com/nidp/saml2/metadata"
$logouturl = "https://myidpurl.mydomain.com/nidp/jsp/o365Logout.jsp"
$cert = New-Object System.Security.Cryptography.X509Certificates.X509Certificate2("c:\temp\MySigningCert.cer")
$certData = [system.convert]::tobase64string($cert.rawdata)


Write-Output $dom $url $ecpURL $uri $logouturl $certData

Set-MsolDomainAuthentication -FederationBrandName $dom -Authentication Federated -PassiveLogOnUri $url -SigningCertificate $certData -IssuerUri $uri -ActiveLogOnUri $ecpUrl -LogOffUri $logouturl -PreferredAuthenticationProtocol SAMLP

So here mydomain.com is the domain in M365 you want to federate and myidpurl.mydomain.com is your IdP URL.  I stuck the Write-Output in there just as a check to verify the variables are set correctly.  This also assumes you have a SINGLE domain to federate. If you have a tenant with multiple top-level domains you want to federate with you need to create individual SAML configurations for each one (and the endpoints all change to have a specifier on them).

You can view federation info with this command:

get-msoldomainfederationsettings

and unfederate with this:

Set-msoldomainauthentication -Authentication managed -domain mydomain.com

I also highly suggest getting a browser plugin like SAML Tracer so you can see what is actually going on with the SAML exchange and troubleshoot issues.  It's pretty hard to troubleshoot without something like that.

Matt