The Genestealer's Medallion
Genestealers in the first edition of the Warhammer 40,000 Rogue Trader tabletop war game.

I expect the medallion makes the Genestealer Patriarch inconspicuous in human societies. "Is that an alien monster?... No, it can't be, he's wearing a medallion."
Rogue Trader (1987)
Genestealers started out in the Alien Creatures section of the Rogue Trader rulebook.

This bestiary included a bunch of fairly generic creatures like dinosaurs, giant spiders and horses. Crotalids were inspired by the availability and relative cheapness of toy crocodiles. There was also a deadly squirrel with the same Weapon Skill as a Space Marine. You can read about the aliens' origins on the Awesome Lies blog
.
Alongside these was the Genestealer.

Genestealer
This enigmatic monster originates from one of the moons of Ymgarl, but has spread throughout space and is threatening to become a real menace. In its native state it is blue, has two pairs of clawed arms, a long muscular tail and a tough leech-like body. Its head is a simple tube full of slobbering tendrils and sharp inward-pointing teeth.
A Genestealer implants its own genetic material in the form of an egg capsule, which is forced into the body of the host by an extendible ovipository normally secreted inside the head. The implantation does not kill the mate immediately, but the implanted egg quickly grows until ready to burst out as an immature Genestealer. Needless to say, this kills the parent/host. Interestingly enough, newly born creatures, although fundamentally Genestealers, will have characteristics inherited from the host parent. Thus a Genestealer/human may have a vaguely humanoid head, or only two arms instead of the usual four, and perhaps its tail will be shortened or missing. A Genestealer of four or more generations consistent human parentage would pass for human on cursory inspection, although a closer look would reveal a bluish skin, sharp pointed teeth and rather disturbing stare. On their home world Genestealers exploit a large leech-like creature called a Csith which is the usual mate. Matings with a Csith always produce natural Genestealers, no matter what its parentage otherwise.
-Rogue Trader
Some of the details would change but the fundamental elements of Purestrains and generations of Hybrids are there. There was a metal sculpt , but it was never released.
In rules terms Genestealers could make implantation attacks which would hatch on a D6 result of 6 per turn. Immature Genestealers could mature by eating other models.
Genestealers lent themselves to either being rampaging monsters or more subtle narrative plots involving Hybrids. Games masters were encouraged to generate their own Hybrid profiles as somewhere between the Genestealer and host profiles. Genestealers could infect anything, including rabid Ptera-squirrels.
Genestealers were Int 3. Not too bright. The intelligence stat dictated what technology a model could use.
Space Hulk (1989)
Genestealers came into their own when they were chosen as the monster Space Marine Terminators faced in the board game Space Hulk developed by Richard Halliwell.
The Genestealers are a race of aliens who seek to conquer the universe. They travel in huge, ancient, nearly derelict vessels, commonly known as space hulks, until they find a suitable planet to 'colonize.'
A victim of the Stealer truly suffers a fate worse than death. Injected with the Stealer’s egg, the victim becomes an unknowing carrier of the Stealer’s DNA pattern, and his children are born as Genestealers. These creatures, in turn, infect other humans, until the entire planet is taken over.
-Space Hulk, 1st Edition
The second expansion, called Genestealer, added plastic Genestealer Hybrid models, perhaps some of the ugliest models Games Workshop ever released. Fortunately, there were some better metal sculpts .

Genestealer Army Lists (1989)
Genestealers are a race of aliens from another galaxy who seek to conquer the Imperium from within.
-Warhammer 40,000: Compilation
With the addition of Hybrid, Magus and Patriarch miniatures, Genestealers had enough models to warrant a 40K army list. Rules were printed across three issues of White Dwarf magazine (WD114/WD115/WD116) later reprinted in the Warhammer 40,000 Compilation book.
Genestealers gained a much improved profile reflecting their close combat prowess. They also became Int 7 but still couldn't work out swords which put them at a disadvantage later when fumble and parry rules were introduced.

There are two army lists - the invasion force and the cult. Players can choose to have either list fall prey to Chaos which can confer chaotic rewards, daemonic possession and summoned Daemons.
Genestealer Invasion Force
The true origin and purpose of the Genestealer kind remains unknown. They enter the galaxy of mankind on drifting space hulks, hoping to contact other species with which they can breed.
-Warhammer 40,000 Compilation
This list only has four entries, Purestrains, 3rd Gen Hybrids, 4th Gen Hybrids and a Patriarch. The other list includes all these things. It did allow you to field lots more Purestrains than the cult list.

Genestealer Cult
Sometimes a Genestealer brood will find it difficult to establish itself as a dominant force within the host society. It is then that concealment and survival become of prime importance. Genestealer features must be hidden, and strange character traits must be concealed or explained away to the inquisitive.
The brood will frequently choose to pose as a religious sect, disguised by wearing voluminous robes, veils or masks, or hidden by the seclusion of a brood in a remote settlement, far from the eyes of curious and the questions of the Imperium.
-Warhammer 40,000 Compilation
This is a much more rounded list which adds a Magus, Brood Brothers and all four generations of Genestealer Hybrids. It also includes those hunted by the Imperium: Rogue Psykers, Mutants and Beastmen. And of course, it has armoured limousines which it was suggested you convert from 1/43rd scale die-cast metal car models.
The Green Brood (1991)

Orks are not an ideal host race for Genestealers and eventually Genestealers who infect them will realise that Orks are a dead end as far as the prospects for furthering the Genestealer species is concerned.
-Freebooterz (1991)
The Ork Freebooterz book devotes a surprising number of pages to the niche Ork Genestealer Hybrids unit. Rules, conversion and painting guide, and a sample unit, Zodgog's Brood.
Tyranids
Genestealers became bio-constructs, the vanguard of the hive fleets, when Tyranids got their own army list. Tyranids deserve their own article.