I can't answer authoritatively, but I have some observations that suggest they're stored in the cloud.
I have two Ledger Nano S devices. One is a hardware backup of the other. During initial setup, I ran into a weird bug with the Chrome App that made one of the BIP32 chain accounts incapable of being labeled. The UI rendering appeared to crash when it tried to display a null label, so the button you'd press to change the label never showed up. The callback that changed the account's balance from the default of zero to its true balance didn't run, either, which was momentarily very alarming.
Anyway, I hoped that the labels lived on the device, so I hard-reset it and set it up again. The prior labels (including the null one) returned. My working theory at this point was that the labels lived in the cloud, but there was also a possibility that they were stored in the Chrome App's local synced storage. To test that theory, I set up the second Nano with the same BIP39 seed using a completely different Google account. The prior labels still appeared on the second wallet. This ruled out storage in the Chrome App. The only place left to store the labels would be the cloud.
So based on this evidence, my theory is:
- Ledger runs a cloud key/value storage service.
- The key is probably a hash based on the BIP32 xpub for the account.
- I hope but can't prove that the value is symmetrically encrypted with something based on the account's xprv. If it's sent or stored in cleartext, then the Ledger team has a lot of very private data about user accounts ("Spending money," "Illegal stuff," "I am Satoshi," etc.).
The service could also have access to account balances, but that's a risk that comes with any wallet connected to an online computer.
By the way, I fixed the null label bug by opening the Chrome App's developer console, confirming that it indeed was throwing an exception, and then modifying the in-memory code to add
if (!label) {label="fixed";} which got me far enough to get to account settings, where I was able to set the label for real. It persisted after that and all was well.
