The story
From the past participle of dye in the wool. The expression comes from the fact that fabric can be dyed in a number of ways. The woven fabric may be dyed after it is complete, or the threads may be dyed before they are woven. When a color is "dyed in the wool," the wool itself is dyed before being spun into threads, so the colour is least likely to fade or change. (Dyes: Webster’s Quotations, Facts and Phrases. Icon Group International. 2008, p. 344.).
Etymology from Wiktionary, CC BY-SA 4.0.