How did the House Elves become so skilled at magic? Was there a training program, or....?
House Elf powers aren't ever explained directly in books or JKR material.
But since no magic user can apparate in/out of Hogwarts (or Voldemort's cave) and elves can, it can be inferred that their power is NOT taught by wizards originally.
JK Rowling replies -> He's a house-elf, they've got powers wizards haven't got (but wizards have also got powers that house-elves haven't). (source: JK Rowling's World Book Day Chat, March 4, 2004)
Q: You say that people cannot Apparate or Disapparate within Hogwarts and yet Dobby manages it, why is this?
A: House-elves are different from wizards; they have their own brand of magic, and the ability to appear and disappear within the castle is necessary to them if they are to go about their work unseen, as house-elves traditionally do (Source: http://www.jkrowling.com/textonly/en/faq_view.cfm?id=73 )
Dumbledore talks about house elves (especially Kreacher) in OOTP chapter 37.
[Kreacher] was bound by the enchantments of his kind,
‘Kreacher is what he has been made by wizards, Harry,’
I believe this hints that the wizards have had their part in what the house elves are like. They've bred them and trained them and magically transformed them until they've reached their current state.