The Shadar-Kai were first introduced in the D&D 3.0 Fiend Folio. Let's walk through what we know about them from each editions.
Type: Fey (Extraplanar)
In Brief: Also known as the Shadow Fey, the Shadar-Kai are a race who are very, very old. In ancient times, they sought to secure the world against the rising mortal races, and forged a pact with a dark power in the Plane of Shadow to seal the world in endless Twilight, in which they would rule supreme.
Something went wrong and, instead of what they wanted, the Shadar-kai ended up binding their souls to the Plane of Shadow, which is constantly trying to eat their souls. This has left them embittered and vicious at the best of times. They can 'stave off' the effects of this curse by actually living in the Plane of Shadow, and it is possible for them to reclaim their souls via magic.
Culturally, they are pretty nasty--they absolutely hate every sort of non-evil Fey and will only ally with evil Fey to hunt good ones, or deceive and do harm to mortals.
Source: Fiend Folio, D&D 3.0, p.150
The Shadar-Kai were not, to my knowledge, updated in 3.5
Type: Shadow Humanoid
In Brief: 3.x Shadar-Kai lore got tossed out a window and rebooted. In this version, Shadar-kai are a "bleak and sinister" culture of humanoids living in the Shadowfell that serve the Raven Queen. I can't find specific lore that says why they are in the Shadowfell in the first place, only that they have been there for "eons." They are no longer "Evil" but are still pretty extreme beings. The Shadowfell makes you very prone to despair and despondency, so the Shadar-Kai do a lot of things to try to ward that off--their lives are a study in extremes, pain, pleasure, intensity, bragging and boasting, and so on.
Source: 4E Monster Manual, p.230, Dragon Magazine #372, p.6
Addendum: Officially, the Shadar-Kai have a different origin in the Forgotten Realms in 4E. In The Realms, at least as of 4E, The Raven Queen does not exist (The FRs are not the default setting of 4E). In The Realms, the Shadar-kai are the result of the Spellplague mingling humans (of the Netherese Empire, who fled the fall of their empire to the Shadowfell) with shadow magic and producing a new race. Their basic attributes and behavior are the same as in the 'Core' 4E world.
Source: Dragon Magazine #391, p.13
Type: Humanoid (Elf)
In Brief: 5th Edition brought The Raven Queen into the Forgotten Realms, and she brought the Shadar-Kai with her. The Netherese Shadar-Kai are being ignored in 5E, so far as I can tell. In this version, the basic day-to-day around the Shadar-Kai is the same as it was in "Core" 4E, if you just remove the word "Human" and replace it with "Elf."
In this version, the Raven Queen was an Elven Queen who was hijacking her way to godhood and the "Shadar-kai" were her most devoted followers. Shenanigans ensued, and she ended up dragging herself and all of her followers into the Shadowfell where she died and was reborn as The Raven Queen. Her followers are cursed to serve her forever which, fun fact, means they are actually true immortals--if they are killed, their souls return to The Raven Queen, who resurrects them.
Source: Mordenkainen's Tome of Foes, Chapter on Elves
I have been entirely unable to find anything resembling an explanation of why the lore around the Shadar-Kai has changed so much between editions.
In 3.0 they were evil fey, 4E they were either humans sworn to the Raven Queen or Netherese survivors touched by the Spellplauges, and in 5E they are Elves soul-bound to the Raven Queen.
This is not terribly uncommon, honestly. D&D does have a tendency to overwrite, ignore, or alter lore between editions.