Phineas Nigellus has a portrait in the Headmaster's study at Hogwarts, and another portrait at Grimmauld Place. Hermione spent her summer and Christmas holidays in OotP in Grimmauld Place along with Harry, Ron, and the Weasley siblings. So it's highly likely he overheard a conversation where one of them mentions Hermione's muggle-born status at some time or another. While this is not mentioned in the book, Rowling doesn't cover every single conversation that occurs in Grimmauld Place at the time, so that could be his source of that information.
It could also be that, as @JanusBahsJacquet mentioned, he overheard a conversation regarding her status in the Headmaster's office, either during Dumbledore's, or more likely, during Snape's time. Let's not forget that Snape was Headmaster at a time when the Dark Lord was ruling magical Britain. Also, because of him supposedly 'murdering' Dumbledore, he would be high in Voldemort's favourite list, maybe even the highest among Death Eaters (especially since Bellatrix and Malfoy were still being punished for the debacle at the Ministry). Hermione was known to be close to Harry, and so the Death Eaters would be putting as much effort into searching for her as for Harry. So some news of her whereabouts might have been passed on to Snape, with the Death Eaters obviously referring to her as a 'Mudblood'. There is a conversation that occurs which might give slight illumination to this:
And now Snape stood again in the headmaster’s study as Phineas Nigellus came hurrying into his portrait.
“Headmaster! They are camping in the Forest of Dean! The Mudblood—”
“Do not use that word!”
“—the Granger girl, then, mentioned the place as she opened her bag and I heard her!”
Harry Potter and the Deathly Hallows, Chapter 33: The Prince's Tale.
So either Snape and Phineas had discussed her before, or Phineas was present in his portrait at the Headmaster's study when Snape discussed her with another person.