Its first appearance, as far as I know, was in Thomas Ravenscroft's publication, Pammelia, 1609, which you can find here. It's difficult to know with Ravenscroft what he took from other collections, from broadsides (there's certainly some of that), or what he wrote himself, as his song publications make no distinction. In the days before copyright, he didn't need to. It's in Ravenscroft's books that we also find the first extant versions of There Were Three Ravens and Three Blind Mice, which I'd say there's a good chance he wrote, for reasons I won't go into here (so as to avoid thread drift). Hey ho specifically is here. Watch out for the moveable clef.