There are a few things in this so I'm going to try to keep it simple:
Firstly, for popular services, I highly recommend using Laravel's official OAuth client library Socialite. It makes registering and authenticating users in Laravel via external OAuth providers super easy and can easily be extended to support custom providers.
This allows you to bypass the need for a password altogether and is one of the main selling points for "Social Sign-In".
There's also a third-party set of integrations for the less common OAuth providers called Socialite Providers - check that out too in case you ever want to give folks another way to login.
When you've got a new user's Facebook/Google token, you should create a new record in your users table. You can store the token with it. (Handling of tokens is a whole other topic that will need to be covered in another post perhaps, because usually these tokens expire
For most services (Facebook/Google etc), their API exposes a secure endpoint (you will need to send the token for the user in the request) that lets you grab a few basic details about the user, such as the name and email address they use on that service. Depending on the scopes requested and the legal agreements in place, you may be allowed to store these details along with the user's record in your own database.
What you absolutely MUST store here is their unique ID for that service as this is what will allow you to determine whether a user is signing in or registering via a given service. So for example, in your users table, you should have a separate column for each service, like google_user_id, facebook_user_id. (Don't forget to index those columns too!)
Now you have some choices to make: it's quite common that a user will forget that they signed up for your service using a particular social account, especially if you have many options available - I've done it myself, forgotten which social network I used to sign up for another app/site.
It can be a bit disconcerting for the user (and annoying for you as the developer/business owner) if they inadvertently choose a different option to the one they used before, only to find that it creates a completely new account instead of logging them in to the account they originally created.
In this case, it's good to try and find a way of matching users up across their different social logins - their email address may be a good candidate for this.
You could also give your users a back-up option by allowing them to set a password directly in your system. This is useful in case any of the third-party login providers you've integrated with become inaccessible from your system or for the user for any reason (e.g. they go down or your integration breaks because of API or SDK changes).
If you do choose to let social sign-in users set a password too, you should probably think about doing this in your on-boarding flow right after they've registered and making it mandatory so that they can't skip it even if they go away and come back later.
Of course, it's best not to forget about people who originally chose to sign up with a password. Seeing social sign-in options available, they may now wish to add these methods to their existing account to make their future logins easier.
This requires a little more thought: should they login with their password first and then gain access to tools to link these accounts? Or can they attempt to sign in and you try to find their account based on the email address? How will you handle weird edge cases where the email address for a social sign-in matches the wrong account?
You will probably want some out-of-band verification, e.g. an email with a one-time unique code to prove ownership.
There's no right answers here as it depends largely on your users, the networks they're more likely to have accounts on and the ones you're prepared to support.
Please keep in mind that I've used the words "you" and "your" a lot here for simplicity, but in this case some of this really applies to your client, as legally speaking it is about their relationship with their users and the social sign-in providers they want to use.
Happy to try and help further as time permits.