Berúthiel was first described in Unfinished Tales. She was of Black Númenórean origin, from "the inland city", somewhere south of Umbar. Her marriage to Tarannon Falastur is believed to have been arranged for political reasons. She is described by Tolkien as "nefarious, solitary and loveless", and she and Falastur never had any children. Eventually, Falastur separated from her and sent her into exile, at which point she returned to her original home.
Berúthiel was most notorious for her cats—in particular, her use of them as spies. This is described in 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."
It may well have been her continual intrigues that led Falastur to expel her. Her name was removed from the Books of the Kings (but not from the memory of Men), and Falastur had her sent out to 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."
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.