My own little theory is that Hordak had escaped from the Horde years ago and went to Etheria, there he learned his magic from Noah. Although once he found technology Hordak slowly turned away from magic. Horde Prime discovers Hordak and gives him one last chance to come back to the Horde, he then joins Horde Prime again and embraces the vast technology he offers him. (unfortunately my theory is very flawed in that it is implied that he trained skeletor magic. Sorry but this is all I can say)
All in all it is difficult to say for sure, the most one can get is theories (so what else is new?). Possibly Hordak met skeletor through a portal spell to Eternia or (and this goes against many theories on keldor/skeletor) he met him on Etheria. It's tough to say, but I am glad that there is a topic on this.