When texture quality is reduced, how is it actually reduced?

Solution 1:

Skyrim comes with what you term low res textures, indeed the "high resolution HD texture pack" was released post general release. Seemingly as with other Bethesda games if the system and the system resources are struggling, the game will load the respective lower texture pack if it needs to, there should be no scaling on the fly, as you say.

Since you have selected the "very high" resolution texture pack and are still getting an at least playable, FPS I wouldn't worry too much.

Solution 2:

Does the game already come with pre-sized textures for each texture level and use them accordingly? Like if I set it to low, it loads all textures from the "low category"?

Yes, and Yes.

Or does it down-scale on-the-fly the hi-res textures the game comes with?

No.

And if it does do that down-scaling on-the-fly

It doesn't.

isn't that a performance hit?

Yes, it would be if it did. But the performance hit would be far less than it would be if your GPU was constantly swapping textures in an out because there wasn't enough VRAM to load the high res textures.