In Ocarina of Time, Skull Kid lived in the Lost Woods. It was said that when a Kokiri kid went into the Lost Woods and actually got lost, they would turn into a child of the forest known as a skull kid. Link befriended one of the Skull Kids by playing Saria's song for it. Also, you could give the skull kid the skull mask, which acomplishes his desire to have a face.
Majora's Mask expanded on that same Skull Kid's story. Link had set out on a personal adventure, looking for an old friend, who actually was Navi. While traveling with Epona in the Lost Woods, Link was ambushed by the Skull Kid wearing Majora's Mask and Skull Kid's two fairies, Tatl and Tael. The actual reason that Skull Kid attacked Link was because Skull Kid was under the control of Majora.
Skull Kid proceeded to steal Epona and Link's treasured Ocarina of Time, and when Link followed him, Skull Kid turned him into a Deku Scrub. Skull kid wears a fake beak so he can have a "face" for that is the main goal of a Skull Kid's life.