Queen Berúthiel was a Queen of Gondor.
She was the wife of King Tarannon Falastur of Gondor, and was noted as being "nefarious, solitary, and loveless". It is therefore of no surprise that Tarannon died childless.
According to the Unfinished Tales:
- "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."
- ― Unfinished Tales, note 7 to "The Istari"
Her name was removed from the Books of the Kings (but not from the memory of Men), and Tarannon had her set adrift on sea in a ship 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."
- ― ibid
In an interview  Tolkien had in 1966 he added the following information on her:
Well, Berúthiel went back to live in the inland city, and went to the bad (or returned to it—she was a Black Númenórean in origin, I guess). She was one of these people who loathe cats, but cats will jump on them and follow them about—you know how sometimes they pursue people who hate them? I have a friend like that. I'm afraid she took to torturing them for amusement, but she kept some and used them: trained them to go on evil errands by night, to spy on her enemies or terrify them.
Piecing all this info together, it can be surmised that Berúthiel was a Black Númenórean from an unnamed Black Númenórean settlement south of Umbar (there were several, mentioned a couple of times but never mapped or named), and that Tarannon probably married her in an attempt to settle the feuds Gondor had with the more southern Númenórean realms in exile. Berúthiel probably returned home, and her expulsion from Gondor must have reignited hostilities between the Black Númenórean realms and Gondor, which eventually lead to the capture of Umbar in Third Age 933 after a new war.
Tolkien disliked cats, and it seems that Berúthiel was associated with evil because of her cats, or vice versa.