Tiefling

How Tieflings looked like prior to 4e.

A corruption-touched race from Dungeons & Dragons, with a lineage stretching all the way back to 2e's Planescape setting, where they were one of the three initially released races for the setting, alongside the githzerai and the bariaur. In contrast to their mostly-forgotten kinsfolk, they have had a huge impact on D&D and been quite decently supported ever since, becoming core races in the 4th and 5th editions. It has to be said, this may be due to their fluff being rather supportive of mary sue-players.

One of the recurring themes of Tieflings is that others find them inherently unsettling. They tend to have Charisma bonuses (representing either their superior ability to intimidate others or the fact that everybody wants to bang the horned chicks, depending on who you ask).

2e, 3.x, Pathfinder

Tieflings are mortals whose lineage is tainted by the blood or essence of a fiend - demon, devil, daemon, whatever - at some remote point in their ancestry. Not an actual fiend's kid, mind, (those are either alu-fiends or cambion, depending on the gender), but one of their descendants. Basically, if a humanoid half-fiend has a kid, it'll probably be a tiefling, and after that the fiendish blood can also skip a few generations. Sometimes, it naturally occurs due to fiendish pacts, either in the pact-ee or their descendants.

In general, tieflings are presumed to be either unable to figure out what sort of fiend was their ancestor, or just inherently prone to fiendish mutation. As a result, their physical displays of fiendhood and their ability modifiers have often had sizeable - we're talking D100 tables, here - random tables to roll on, depending on edition and sourcebook.

That said, there is a little support for more "pureblooded" or "recognizable" tieflings. Pathfinder has a whole sourcebook called Blood of Fiends which features not only the inevitable "random tiefling power/appearance" tables, but also details on all of the various kinds of tiefling that can be spawned from specific classes of fiend - demon, devil, daemon, demodand, rakshasa, oni, kyton, etc. Additionally, tieflings are one of only two non-core races usable in officially-sponsored play (the other being the aasimar), and are common in-setting around both the nation of Cheliax (whose demon-summoning ways creates lots of them and whose Nazi-esque human-supremacist social policy discriminates against them) and around the Worldwound. (You, uh... you don't want to know what goes on around the Worldwound.)

Naturally, this lineage begged for grid-filling in the form of the aasimar (celestials) and genasi (elementals), though 3.5 would go another step by adding in "planetouched" races to reflect the outsiders of the Morally Neutral planes too.

Though officially all tieflings can spring from all manner of humanoid races, most writeups tend to either focus on the human tieflings or make it so that the twisting influence of their fiendish blood defines them "more" than their parents being non-fiends. That said, 3.5 Forgotten Realms did do up the Tanar'rukk (orc-descended tieflings) and the Fey'ri (elf/succubus tieflings).

4e & 5e

In 4e D&D, tiefling popularity was recognized and so WoTC decided to dump one of the less popular player races (or so they thought, anyway), the gnome, and make it a core race. But they figured that a race based on "your granddaddy/mommy was a monster from the Lower Planes" wouldn't really be that common. So, instead, they redesigned their tieflings to be the magically corrupted descendants of an evil empire that embraced diabolism and loyalty to Asmodeus to hold onto their power. When their empire fell, they were left scattered and corrupted into the tieflings. As part of this, they got redesigned to a more unified look, with reddish skin, glowing eyes, tails and horns, to make them appropriately "devilish", as opposed to the more grab-bag look of editions past.

D&D Next more or less follows in 4e's footsteps, though it's a bit vaguer on the details as to how they were corrupted and more explicit on the fact that the look of their tails and horns are variable.

Although the Warlock came out in 3.5, it is 4th edition that has really pushed the tiefling/warlock racial to class matchup.