Where are the admin notifications stored?
They aren’t. Admin notices have no storage unless you implement it yourself for your plugin/theme.
WordPress provides hooks and styling for displaying admin notices, but that’s it. It might provide styling for dismissible admin notices but it provides no storage or registration mechanisms for persistence.
And when a user dismisses one, where is that being recorded?
It isn’t, native WP admin notices don’t provide this, it’s implemented by the plugin/theme author. They might store this in a cookie, local storage, user meta, etc, you would need to ask each plugin/theme vendor individually. There is currently no general mechanism.
As an aside, there is a feature plugin for creating a notification centre in core, but at the time of writing it has not been merged, and its status is uncertain. You should give it a look.