1. Storage of Keys, Addresses etc
How exactly is all this stored?
In General
Any way that the developers of a particular wallet want. It is likely that different wallets store their data differently.
In Bitcoin core, for example.
The wallet software named "Bitcoin core" will store the private keys in the wallet.dat file in the specified or default data directory. The default is %APPDATA%/Bitcoin/ or ~/.bitcoin/ depending on platform. If a wallet password is provided, the key data is stored in encrypted form with the password being the encryption key (possibly indirectly and probably using AES IIRC).
The addresses generated are stored in the same file but need not be encrypted.
I don't know if the full derivation paths are explicitly stored. I imagine that at least the least significant digits ought to be stored along with each derived address. Maybe someone can comment.
BDB vs SQLite wallets
The overall organisation of this file has changed and is based on simple key-value database libraries, initially Berkeley-DB (BDB) and more recently SQLite AFAIK.
Descriptor vs non-Descriptor wallets
The keys and values have changed from the original form to a "descriptor" form. So there are non-descriptor wallets and descriptor wallets.
HD vs non-HD wallets
There was also a change to Hierarchical Deterministic (HD) wallets from the original non-HD wallet.
2. Derivation Paths
I see that all addresses are identified using a path naming convention. Does that mean that all the paths are stored, and in a scenario where an address needs to be reused, it is regenerated each time?
Those are implementation details. I don't know how Bitcoin core or other wallets handle this and I believe anyone writing a wallet should make their own decisions.
If writing a wallet app, I would probably explicitly store all generated addresses and paths. Some other people would do something very different.
3. Further reading:
