When do I create the Custom Post Type, does it only need to be done once when the plugin is installed (so once), or do I need to do it each time in the constructor? Or does it not matter?
Post types and taxonomies have to be registered on
'init' for each request. Even the built-in post types are registered this way.
The posts for your post type are stored permanently in your data base.