Folklore
The Night's King is a well-known character. While the TV series may not have mentioned that title before, in the books it is clear that more people than Bran know of him:
No, Bran thought, but he walked in this castle, where we’ll sleep
tonight. He did not like that notion very much at all. Night’s King
was only a man by light of day, Old Nan would always say, but the
night was his to rule. And it’s getting dark.
—A Storm of Swords
The Night's King is explicitly described as an entity mentioned in stories:
The gathering gloom put Bran in mind of another of Old Nan’s stories,
the tale of Night’s King. He had been the thirteenth man to lead the
Night’s Watch, she said; a warrior who knew no fear.
—A Storm of Swords
Given that Old Nan, who told Bran of the Night's King, has (so far as described in the books) no personal experience with the Night's King, nor (as a servant) access to any obscure texts, we can assume that this is a well-known tale.
Martin has said that the Night's King may not be alive in the books, but in doing so makes it clear that he is well-known:
As for the Night's King (the form I prefer), in the books he is a
legendary figure, akin to Lann the Clever and Brandon the Builder, and
no more likely to have survived to the present day than they have.
It seems reasonable to assume (in the absence of contradictory evidence) that something similar is true of the TV series: The Night's King is a well-known folkloric figure.
