Perhaps the simplest answer is from Dobby -
"Dobby, what're you doing here?" Harry said in amazement.
"Dobby has come to work at Hogwarts, sir!" Dobby squealed excitedly. "Professor Dumbledore gave Dobby and Winky jobs, sir!
"Winky?" said Harry. "She's here too?"
Harry Potter and the Goblet of Fire, Chapter 21 'House Elf Liberation Front'
"How long have you been here, Dobby?" Harry asked as Dobby handed around the tea.
"Only a week. Harry Potter, sir!" said Dobby happily. "Dobby came to see Professor Dumbledore, sir. You see, sir, it is very difficult for a house-elf who has been dismissed to get a new position, sir, very difficult indeed- "
At this, Winky howled even harder, her squashed-tomato of a nose dribbling all down her front, though she made no effort to stem the flow.
"Dobby has traveled the country for two whole years, sir, trying to find work!" Dobby squeaked. "But Dobby hasn't found work, sir, because Dobby wants paying now!"
The house-elves all around the kitchen, who had been listening and watching with interest, all looked away at these words, as though Dobby had said something rude and embarrassing. Hermione, however, said, "Good for you, Dobby!"
"Thank you, miss!" said Dobby, grinning toothily at her. "But most wizards doesn't want a house-elf who wants paying, miss. 'That's not the point of a house-elf,' they says, and they slammed the door in Dobby's face! Dobby likes work, but he wants to wear clothes and he wants to be paid. Harry Potter....Dobby likes being free!"
The Hogwarts house-elves had now started edging away from Dobby, as though he were carrying something contagious. Winky, however, remained where she was, though there was a definite increase in the volume other crying.
"And then, Harry Potter, Dobby goes to visit Winky, and finds out Winky has been freed too, sir!" said Dobby delightedly...."And then Dobby had the idea. Harry Potter, sir! 'Why doesn't Dobby and Winky find work together?' Dobby says. 'Where is there enough work for two house-elves?' says Winky. And Dobby thinks, and it comes to him, sir! Hogwarts! So Dobby and Winky came to see Professor Dumbledore, sir, and Professor Dumbledore took us on!"
Dobby beamed very brightly, and happy tears welled in his eyes again.
"And Professor Dumbledore says he will pay Dobby, sir, if Dobby wants paying! And so Dobby is a free elf, sir, and Dobby gets a Galleon a week and one day off a month!"
"That's not very much!" Hermione shouted indignantly from the floor, over Winky's continued screaming and fist-beating.
"Professor Dumbledore offered Dobby ten Galleons a week, and weekends off," said Dobby, suddenly giving a little shiver, as though the prospect of so much leisure and riches were frightening, "but Dobby beat him down, miss....Dobby likes freedom, miss, but he isn't wanting too much, miss, he likes work better."
Dumbledore had recently employed both Dobby and Winky, and would have known Winky's employment history. I imagine he would particularly remember Winky as Arthur Weasley notes that Barty Crouch firing his House Elf, after being found with a stolen wand that had conjured the Dark Mark, would be quite scandalous and of particular interest to Dumbledore:
"Crouch is very lucky Rita hasn't found out about Winky," said Mr. Weasley irritably. "There'd be a week's worth of headlines in his house-elf being caught holding the wand that conjured the Dark Mark."
Harry Potter and the Goblet of Fire, Chapter 10 'Mayhem at the Ministry'
Dumbledore generally seems more aware of the house elves in his employ compared to most wizards, at least based on his treatment of Dobby, Kreacher and Winky.