- "I fear it would be of little interest to you, my lord, a ponderous tome..."
- ―Grand Maester Pycelle to Eddard Stark
The Lineages and Histories of the Great Houses of the Seven Kingdoms is a book detailing the history of the Great Houses of the Seven Kingdoms, including the lineage and appearance of all heirs, with illustrations of each house's individual sigil. It was written by Grand Maester Malleon.
It is quite a ponderous tome; arranged as a chronicle instead of a narrative, it is primarily concerned with dates, marriages, and lines of descent. Persons mentioned in the book are also given brief physical descriptions (from surviving sources), along with important general facts about their lives and the manner of their deaths.
After his daughters note that Joffrey Baratheon has blonde hair, Lord Stark checks the Lineage and Histories, and discovers that all members of House Baratheon are described as "black of hair", except for the "golden headed" Joffrey. This, coupled with Robert's bastard son, the black-haired Gendry, claiming that his mother was blonde, leads Ned to realize that Joffrey and his siblings may not be Robert's biological children, and thus not rightful heirs.
Behind the scenes
Because the book first appears in "Cripples, Bastards and Broken Things", the information in it was created by Bryan Cogman, who wrote that episode (though it later reappears in "A Golden Crown"). That is, the contents were not an invention of the art department: Cogman created all of the information in the prop book, then Jim Stanes physically copied what Cogman wrote into the prop itself, in medieval handwriting.
As Cogman explained, he created entries for four noble Houses, two pages each, for a total of eight pages of content (the rest is just repeats of this or blank pages). The families were House Umber, House Royce, House Targaryen, and House Baratheon. Ned Stark reads aloud from the Umber entry in episode 104, and from the Baratheon entry in 106. Bits of the Targaryen entry can be seen as Ned leafs through the book. Cogman explained that in the original draft of the episode there was "a bit from House Royce" as well, but it was cut, as was another scene with the Targaryen entry (by "a bit", he might have meant a point when Ned actually reads part of an entry aloud).
Cogman stated that he used as many reference sources as possible, searching through both the books and researching Westeros.org's A Wiki of Ice and Fire. There are large gaps in the history of the story, however, for which Cogman simply had to make names up - i.e. it's possible that even George R.R. Martin has not currently planned out the entire lineage of House Umber from the Targaryen Conquest to the present, though the royal Targaryen lineage is better detailed in the books. For the minor names he had to make up, Cogman said he snuck in a few in-jokes using names derived from fan messageboards. He also said it was fun coming up with various diverse ways that minor characters had died.
In the books
In the A Song of Ice and Fire novels, The Lineages and Histories of the Great Houses of the Seven Kingdoms, With Descriptions of Many High Lords and Noble Ladies and Their Children is an old book written by Grand Maester Malleon. It doesn't mention the current Baratheons or Lannisters, but it mentions that throughout written history all Baratheons have been black-haired and that, likewise, every recorded union between Baratheon and Lannister has produced black-haired children.