Who is Queen Berúthiel?

To quote from Tolkien Gateway:

Berúthiel was a Queen of Gondor in the early part of the Third Age. She was the wife of King Tarannon Falastur, and was noted as being "nefarious, solitary, and loveless". It is therefore of no surprise that she and Tarannon produced no heirs.

About her cats:

Berúthiel loathed cats, but they became attracted to her for precisely that reason. They followed her around, and eventually she took advantage of their company by enslaving and torturing them. In total she had ten cats, nine black and one white. Berúthiel set the black cats to spy on the Men of Gondor and the white cat to spy on the black ones. She managed to learn many dark secrets about the realm and its people by conversing with them and "reading their memories". These cats were infamous among the Gondorians, but they dared not touch them; however, Men would curse whenever they saw one pass by them.

Her marriage did not end well:

Eventually, Tarannon exiled Berúthiel from Gondor due to her deeds and erased her name from the Book of the Kings. He sent her and her cats back to her southern homeland on a ship that "was last seen flying past Umbar with a cat at the masthead and another as a figurehead on the prow".

Source: http://tolkiengateway.net/wiki/Ber%C3%BAthiel