Nevermind, I figured it out. Just needed to think about it a little more. The bottom 4 bits determine the first and second palettes available, and the top 4 bits determine the third and fourth palettes available. All of the palettes start at 1, and each step up in bits adds 2 to that.
So for example, at the town of Baron the NPC palette byte is 10. This means the bottom four bytes are 0000, so the first and second palettes available are palettes 1 and 2. The top four bytes are 0001, so the third and fourth palettes available are palettes (1+2) and (2+2) = 3 and 4. In the Village Mist, the top four bits are 1001, so the third and fourth palettes are (1+9*2) and (2+9*2) = 19 and 20.
We have EVEN MORE themes now, but some old ones are gone...