You'll need to be an admin of the workspace you want to connect.
Next, you need to create a bot in your Notion account. Go to the Integrations tab in Settings. Click on the link that says Develop your own integrations.
Give your bot a name, click to create it, then click to reveal your secret token. Copy this as you'll need it back over in Zapier.
In Zapier, click to create a new zap, select Notion as either your trigger or action step, and on the next tab, you'll be prompted to connect your Notion account using the token you just copied.
Once successful, the final thing you need to do is invite your Notion bot to the board you want to connect to. Do this using the blue button on the top right of your Notion board - the bot you created will be an available option (make sure to allow edit access).
If you're a more visual learned, check out this video guide from Vensy Krishna where she steps through connecting Notion to Zapier and creating new database items fro Google Forms submissions (skip to 8:28):
What sort of things can I do with Notion's Zapier integration?
Integromat has a Notion integration which is notable for having more functionality than Zapier's, including the ability to retrieve content from and add to existing pages. It also has a "Make an API Call" action step which allows you to utilise all the Notion API endpoints.