The short answer is that even though they are fully authenticated, you still need to prompt with a "registration" screen to get their profile preferences. Something like:
Hello XX_New_User,
We are not able to find an existing account for this username.
- Would you like to create a new account for XX_New_User?
If you believe you already have an account, maybe it is associated with a different
Facebook/Google username? If so, click "cancel" and log in with another username.
If you have an account and you would like to add this username to that account,
then click "cancel", log in with the old username, and use the Add options to add this username.
If they choose to create a new account, then of course you prompt for whatever preferences you need to record at that time.
I worked on a system for a long time where we transparently and automatically made new accounts whenever a new person logged in, but this was a problem. Someone would log in with their Facebook ID and set up a bunch of stuff. Later, they would log in with their Google ID and without their knowing it, get a new, empty account. They thought the system had lost all their settings. It is critical that you let the user know when you are creating a new account, and make this a distinct action.
Analysis
Using cloud-based SSO techniques requires you to turn around the thinking on the normal registration process. In a "traditional" application, when a user registers their authentication credentials (password), they also set some preferences in their "profile" in the same step. Both the authentication credentials and profile information are often kept in the same place.
When a program leverages Facebook/Google to do the authentication, it does not need to gather a password, but it still has to gather information for their profile. If it doesn't find a profile (e.g. an account) then it must prompt them to create one. The prompt is important because they may have multiple online logins, and they may have used the wrong one.
Trap: Some programmers jump to the conclusion that saying whether a person has a profile or not is a security risk / information leak. In a "traditional" application, you would never say whether a user exists or not to an unauthenticated visitor. However, there is no security risk here because after authentication from Facebook/Google, you know for certain that the user is a specific person. Even though you do not have an account for the person, because of the SSO, you do have assurance that only the person in question can see the result. I mention it here because this is a common mistake among good software architects.
Note that the message offers to add a login to the profile. In a "traditional" application, there is only one identity per profile, but when you use SSO, there will be the possibility that someone will want to change their identity in the future, and keep their profile information. Just because I change my Google ID does not mean that I want to set everything up in your application again. There should be multiple logins (usernames) in a profile, and there should be a way to add and delete them. Be sure that they are properly authenticated before making any of these changes.
I cover some other aspects of migrating an application from a "traditional" mode, into a SSO mode, in my blog post SSO: What is it?
