When a new user signs in using SSO, it creates a new account with a new application and doesn't add the user to our applications. Is this how it works?

Yes, that’s how it works, the owner of an application will need to invite users from the "Team" page of their dashboard. If invited users don’t have an Algolia account yet, they have to complete the registration flow, which indeed includes creating a free application.