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.
3.0
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 updated in 3.5 with the article "Ecology of the Shadar-kai" in Dragon Magazine #337.
4E
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. They first debuted in "Wizards Presents; Worlds and Monsters", one of two "preview" softcover books released to try and give players a head's up on the mechanical and lore changes that 4e would be making. They are characterized as humans who were so afraid of death that they sought immortality by migrating to the Shadowfell, where they pacted with the Raven Queen and agreed to live by her example in exchange for getting what they wanted. 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. This is further justified by their pact with the Raven Queen; so long as a shadar-kai can stave off ennui, they will remain young and vibrant, but as they surrender to apathy and boredom, they literally fade away into nothing.
Source: 4E Monster Manual, p.230, Dragon Magazine #372, p.6, Wizards Presents: Worlds and Monsters, p.53,
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
5E
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
Transitions
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.