Go to admin page (Setup):

Open Object Manager (1 or 2):

Click "Create" -> "Custom Object" (3):

After you click a New Custom Object, you will need to enter the appropriate information and Save the object:

The fields you add should answer two questions:

1. What does the person doing this step need to know?
2. What information will the person doing this step need to provide in order to move the flow forward?

Go to newly created Custom Object and navigate to "Fields and Relationships" tab (4). Click "New" button (5) to add a new Custom Field:

"New Custom Field" wizard will navigate you through creation process - select field type, set it's name, label and other properties, specify which user profiles will have an access to this field and page layout(s) which this field will be added automatically (by default it will be a layout of proper object record).

In the Work-Relay Settings, go to Objects Settings and add the object to allowed here. See proper article.