I couldn't find it easily in the documentation, although it's there they don't say the keyword "Gutenberg" anywhere.
The keyword you have to look in the documentation is rest API.
In your register_taxonomy() or register_post_type() arguments you need to set:
'show_in_rest' => true
Please notice you need it the parameter first and foremost the Custom Post Type and then, in case you have Custom Taxonomies, also there. Or they won't show up in Gutenberg's sidebar.