he reference is to Book II, Ch 4 "A Journey in the Dark": " 'Do not be
afraid!' said Aragorn. There was a pause longer than usual, and Gandalf and
Gimli were whispering together; ... 'Do not be afraid! I have been with him
on many a journey, if never on one so dark; ... He is surer of finding the
way home in a blind night than the cats of Queen Beruthiel.' " [FR p. 325]. This is a striking case of Tolkien's creative process. It seems that the name meant nothing when it first appeared: it just "came" as he was writing the first draft of the chapter. Later, however, he "found out" whom she "actually" was, his conclusions being reported in UT.
She was the wife of King Tarannon of Gondor (Third Age 830-913), and was described as "nefarious, solitary, and loveless" (Tarannon's childlessness was mentioned without explanation in the annals). "She had nine black cats and one white, her slaves, with whom she conversed, or read their memories, setting them to discover all the dark secrets of Gondor,... setting the white cat to spy upon the black, and tormenting them. No man in Gondor dared touch them; all were afraid of them, and cursed when they saw them pass." Her eventual fate was to be set adrift in a boat with her cats: "The ship was last seen flying past Umbar under a sickle moon, with a cat at the masthead and another as a figure-head on the prow." It is also told that "her name was erased from the Book of the Kings (`but the memory of men is not wholly shut in books, and the cats of Queen Beruthiel never passed wholly out of men's speech')." [UT, pp 401-402]