How did Windows 95 apply icon themes?

It uses the registry for desktop icons. I am pretty sure it only changed the desktop icons

Yes, all of this can be done with registry settings.

Even though the plus themes only changed a few icons, like "my computer", network, trashcan and "My documents" (on Windows 98) a lot of icons can be changed with registry settings.

Ok, now I get what you mean.

These are no additional icons that the plus themes can change but it's rather a registry setting that will be applied by installing the Plus Package (there is a new tab in the display properties called "Plus" and there is one setting called "show icons with all possible colors" or something like that)

That setting will enable "high color" mode for icons and that's what can be seen in your screenshot.
But you wouldn't actually need the plus package to achieve this and the plus themes can't change all the icons.

But as I said, it is possible to change a lot of icons with registry settings, even in Windows 10 and 11 but it's a lot of work.

You don't actually need to modify shell32/imageres to change drive and default folder icons even in Windows 10. In my previous install about 3 years ago i did exactly that. I don't exactly remember what keys do this but I found them on tenforums, i think. So Plus using registry for this absolutely makes sense.