A decoy bird, or a police informer, or criminal's look-out or decoy.
Most reference sources say that this expression derives from the hunting practice of fixing a dead or replica pigeon on to a stool to act as a decoy to attract other birds.
What the stool in question was isn't entirely clear. It certainly wasn't the three-legged piece of furniture we now know, but one of the many other meanings of the word. In the 16th century a 'stoale' was the base of a tree - what we would now call a stump, just the place for a decoy bird to sit. It is also possible that 'stool' is derived from 'estale', which is an early French word applied to a pigeon used to entice a hawk into a net. It isn't far from 'estale pigeon' to 'stool pigeon'.
All of that seems quite straightforward, except for the fact that the term 'stool pigeon', or 'stoolie', doesn't appear in print until the 19th century and in a completely different context. It is first used in American publications and referred to criminals who lured others into crime rather than to decoy birds. The earliest example I can find of the expression is from May 1816 when it was used in the Gettysburg paper The Adams Centinel, in a story about fraudulent paper-makers, that is, counterfeiters. Unfortunately, the print quality of the paper make it difficult to read the full context, but it does describe someone involved in encouraging the passing of counterfeit banknotes as a 'procuror or stool pigeon'.
There are examples of decoy ducks being described as 'stools' from 1825 onwards, but the term 'stool pigeon' isn't used with that meaning until 1871, when M. Schele De Vere listed it in Americanisms; the English of the New World:
Stool-Pigeon... it means the pigeon, with its eyes stitched up, fastened on a stool, which can be moved up and down by the hidden fowler.
It could be that decoy ducks have been called 'stool (or estale) pigeons' since the 1500s but no one wrote the terms down, although that seems rather unlikely. What we do know is that the current meaning of informer came into being in the USA around the middle of the 19th century. The Sheboygan Mercury printed a piece in August 1851 about the prevailing political situation in Italy:
"Everyone fears that his confederate may prove a traitor... and avoided as a Police stool-pigeon and spy."
The most likely explanation of the phrase's origin is that it was coined to describe those police informers who hung around bars (on stools no doubt) in order to pick up underworld gossip but that the name was influenced by the earlier, but as then unamed, hunting decoys.
See other phrases that were coined in the USA.