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 the 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 includes creating a free application.