Dyes seem to be found per difficulty level, and are random within the the game as to what colors you find with what merchants
Each difficulty level will have new dye colors in addition to the dyes from the difficulty levels below it
Normal: Aquatic (Light Blue), Spring (Light Green), Tanner's (Brown), Winter (Light Grey)
Nightmare: Cardinal (Red), Royal (Light Purple), Desert, Ranger (Green), Autumn (Orange)
Hell: Lovely (Light Pink), Elegant (Dark Pink), Marine (Blue), Summer
Inferno: Gold, Inferno (Red), Abyssal (Black), Purity (White), Forrester (Green)
The only exception seems to be the Act I dye merchant in New Tristan. He doesn't seem to live by the same rules than the other Dye merchants do, although I haven't quite figured out what his rules are.
Normal: Green, Brown, and Light Grey only
Nightmare: Wasn't paying attention
Hell: Only had Normal + Nightmare colors until either Act II, or a specific point in Act I. I can't remember which, but do remember being disappointed that he didn't have new colors, and know I spent quite a bit of time in Act I and checked his colors many times
Inferno: Had two new colors the first time I saw him, so perhaps I just had bad luck in Hell?