It's not really the Customizer that stores the changes, sort of. All changes to a theme's settings are done by the theme settings code, and are stored (usually) in the wp-options table (although a theme might have it's own table where it stores settings).
So, if you make changes via the theme's Customizer interface, the theme stores that in the database. If you change to a new theme, there will be settings for that theme that are stored in another spot in the database. Then if you change back to the first theme, it should read the settings that you set before.
Depending on the theme, uninstalling/deleting the theme might remove all the settings for that theme, so if you reinstall that theme again, you'll have to start all over.
Some themes may 'share' settings between themes, but again this is all the responsibility of the theme's code, which uses the Customizer API to display and save settings.