Best practice for new user notification when using Federated SSO

Best practice is to

Turn on My Domain This creates a user-friendly URL which is the same for all users in the org: https://[mydomain].my.salesforce.com One of the advantages of MyDomain is that you can turn off non-SSO logins which lead to
Turn off 'native' SFDC login (aka Login Page authentication service) under Login Page Settings in My Domain. When your users go to https://[mydomain].my.salesforce.com , they'll be redirected to your SAML identity provider.
Note that anyone can still login with their SFDC username/password from https://login.salesforce.com but they no longer see the login page by default. Turning off login.salesforce.com is also possible via MyDomain.

As far as how to notify the user, workflow-triggered email is a good way to go. The User object is usually not a good trigger point. To be productive in SF you typically need more than just a user account but perhaps your org is simple enough so you can trigger from User.