How/Why/When did the house elves start serving wizards? I tried on my own to find the answer but I couldn't find anything relevant to my subject but I am bad at searching.
House-elf enslavement predated the Founding of Hogwarts (c. 990 AD), and was brought to Hogwarts by Helga Hufflepuff, (although she didn't start the enslavement.)
This was most clearly by J K Rowling in a Pottercast interview.1
J.K. Rowling (JKR): This had better not be about House-Elves.
Melissa Anelli (MA): Jo, it is! I'm sorry! It is.
Sue Upton (SU): Hey, Jo! Hello!
John Noe (JN): Hey, Jo!
JKR: What? House-Elves? Go on then.
MA: Still. Still. They are still arguing about this, and I'm sick of it, and we need you to answer it so bad.
JN: What I'm telling Sue is that, if she remembered from when we talked about this in New York1, Jo said that Helga Hufflepuff was a plantation owner of the House-Elves ....
SU: Yeah, but she gave them refuge! Refuge! R-E...
SU: She didn't enslave them.
JKR: Yeah, it's a complicated issue, you know? I would say that Hufflepuff gave... Hufflepuff did what was the most moral thing to do at that time, and we are talking about over a thousand years ago. So that would be to give them good conditions of work. There was no kind of activism there, so no one's gonna say, "Here's an idea. Let's, let's free them. Let's, uh, let's pay them." It was just "well, we'll bring them somewhere that they can work and not be abused."
SU: See? She did not go around with like a whip and say "Yaaah! You must work in the kitchens!" you know?
JKR: Definitely not, no. That would not be... No, no. Definitely not.
SU: See? Woohoo! Thank you, Jo.
(Anelli, Melissa, John Noe and Sue Upton. "PotterCast Interviews J.K. Rowling, part one." PotterCast #130, 17 December 2007. (transcript))
There is currently no more information than that.
1: This was previously revealed by J K Rowling during the Open Book Tour at Carnegie Hall in a conversation with the Leaky Cauldron. No transcript or recording exists to the best of my knowledge, but it was talked about in Pottercast #122 (jump to 12:55) (transcript)
(summed up by Accio-Quote as "Helga Hufflepuff offered the house-elves refuge at Hogwarts, though conditions there were slave-like too, if a bit kinder than elsewhere.")
Houselves are "discovered" on Pottermore, in Book 4, Chapter 14, The Unforgivable Curses. The text says:
The practice of house-elves being attached to wizarding families goes back centuries.
That's pretty much the full extent of the data on the start of House-Elf service that I was ever able to find, in books, interviews or Pottermore.
We can probably idly speculate that the data isn't there both because Wizards don't treat House-Elves as important and thus didn't bother remembering or telling how things started (just like there's no note of how wizards started to use owls for post that we were given).