They are giants sleeping in the earth. They are the children of Azeroth's formation, creations of the Titans, cursed by the malevolent power of the primordial Old Gods to decay from their once nigh immortal forms of iron and stone. They are the subjects of Ymirion, he who turned away from his gods the Titans themselves in the face of his people's degradation. And most of all, they are the forerunners of humanity in the Warcraft setting.
The origins of the vrykul we see throughout Northrend are relatively simple, and yet remarkably complicated for that. Each Vrykul now alive is either a semi constructed being made in the creation forges of Ulduar (when you enter Ulduar's Halls of Lightning you can even see an army of Iron Vrykul waiting to be 'awakened' as it were) or is descended from one so created in the distant past, when the Titan Watchers were set to guard the defeated Yogg-Saron in his prison city of Ulduar itself after the discover of the Curse of Flesh. Alongside the Aesir and Vanir giants (including giants like the Sons of Hodir) and the various Earthen and Mechagnomes, the vrykul served the Watchers of Ulduar for untold millennia until the Prime Designate Loken succumbed to corruption and became a slave of Yogg-Saron.
During the Tribunal of Ages encounter, the history of Azeroth is outlined from the Titan point of view. We learn that after the defeat of the Old Gods but at some indeterminate point before the rise of races like the night elves or trolls, Loken either directly or indirectly instigates a war between the various creations of the Titans that spans the globe, and uses this war to place the majority of 'seed races' (ie those created by the Titans, including vrykul) into stasis.
It's interesting that even the Tribunal doesn't know why the Aesir and Vanir giants went to war. It clearly suited Loken's purposes for them to do so: perhaps it's tied into the means by which Loken managed to overwhelm the other watchers (save Thorim, who would brood atop his temple for eons, and Tyr, who is at present still unknown) and gained sole control of Ulduar, and thus free to plot his new master's freedom.
This much is clear. Alongside the Aesir and Vanir giants, the earthen and the mechagnomes, the vrykul were created by the titans, affected by the Curse of Flesh, and eventually involved in a planet spanning conflict at the manipulation of Loken that led to the majority of their kind being placed in stasis in various 'holding facilities'. It's possible that Gjalerbron was one such holding facility or had its origins there, as when adventurers from the Alliance or Horde go there they can find many vrykul in a state of suspension that they can either be awakened from or killed in. Similarly, Icecrown Glacier's Halls of the Ancestors also holds many vrykul in a kind of stasis.
At some point after this war, the vrykul living in Howling Fjord led by King Ymiron (known as the Dragonflayer Clan) were either awakened from this state or managed to avoid it to lesser or greater degree. While these vrykul were somewhat isolated from their fellows (the Dragonflayers have settlements in both the Grizzly Hills and Howling Fjord and seem to have either subjugated or allied with the Winterskorn tribe, also in Howling Fjord) they, too, ultimately suffered from the degenerative effects of the curse of flesh.
The quest Echo of Ymirion shows two vrykul parents with a child that to them seems hideously deformed, weak and ugly, and far too puny to ever be a vrykul, and players can watch their decision to defy the edict of King Ymirion and refusal to put their child to death. Instead, they choose to hide their deformed offspring somewhere where it can grow to adulthood safely. Later in the quest Anguish of Nifflevar, players watch as Ymirion turns his back on the Titans, believing the curse of flesh to come from them and not the Old Gods at all. (He doesn't actually even mention the Old Gods, which makes me wonder if this was all part of how Loken got the various creations of the Titans to make war in the first place, by convincing those cursed by the Old Gods that it was instead the Titans who had so cursed them.)
So imagine you are one of the vrykul who has sired or given birth to one of these disfigured runts. If you don't kill your child, you yourself will be put to death in Gjalerbron alongside the slumbering bodies of your own people. What do you do?
We don't really know, but from what Thorallius the Wise and the players themselves discover, some vrykul clearly decided to save their stunted, half grown children and hide them somewhere their own people couldn't find them. It is these vrykul who are somehow the ancestors of humanity, possibly the direct ancestors of the Arathor clans that became the first human nation long after the Sundering.
We also know that the vrykul returned to stasis perhaps out of desperation to prevent the curse from further ravaging them, and that many of them, their faith in the Titans lost, eventually found a new god to follow. What's interesting in looking at how the vrykul have come to serve the Lich King is how terrified they are of what they see as the ravaging change from their primordial roots as a seed race of Titan origin through the curse of flesh to a state like that of the very humans who produced Arthas Menethil in the first place. How willing they are to let the Lich King test them, and how eager they are to stop any possibility of their race changing from what it is now by the method of being frozen forever in undeath.
We as yet don't really know how the Kvaldir, or sea vrykul, fit into this. We discussed them when talking about water elementals since they seem to have a connection to Neptulon and his kraken minions, which means that they might have turned to the elementals who once served the Old Gods in a similar way, forsaking the Titans for anyone who might be able to prevent them from turning into humans. (Kvaldir are so divorced from fleshly existence that killing one causes it to explode into seaweed and water.) It's also unclear how different the frost vrykul are from their more fleshy relatives, but Skadi serves King Ymirion in Utgarde Pinnacle so there's at least some connection through the Lich King. Yet some still serve the Titans... Thorim is still an object of veneration by the Hyldnr vrykul, for instance, and it appears new vrykul untouched by the curse were churned out by Loken in Ulduar into recent times. Arthas' vrykul can be found in the massive Utgard complex, in Gjalerbron, and throughout Jotunheim on the glacier. They also infest the wing of the Icecrown Citadel where Dreamwalker is kept prisoner.
There's a lot more yet to learn about the ancestors of humanity... how did they get from Northrend to the Eastern Kingdoms? How long ago did they leave? How many still sleep in stasis below the surface of the earth, and do they just lurk in Northrend or could they be found elsewhere?