This shuffle seems first to have appeared in the anonymous gambling text, A Grand Exposé of the Science of Gambling, 1860, p. 4 of the 2010 edition. The author describes the shuffle in conjunction with a sanding technique to facilitate a perfect weave. This was essential because the trimming of mid-nineteenth-century cards left rough edges that worked against perfect interlaces. This sanding approach was described in newspapers of the late 1800s, such as Chicago's Inter Ocean, July 10 1875, p. 5; and Brooklyn's Standard Union, Dec. 8 1888, p. 5. Interestingly, Alex Elmsley rediscovered the idea of sanding the edges of the cards to make faro shuffles easier for the British cards of the time; see The Collected Works of Alex Elmsley Vol. 2, 1994, p. 295. The quality of playing cards eventually improved so that sanding was no longer necessary.
Two early contemporaneous works on crooked gambling that described the faro shuffle (without sanding work) were Joseph Koschitz’s Koschitz’s Manual of Useful Information, 1894, p. 26; and John Nevil Maskelyne's Sharps and Flats, 1894, p. 204. Both descriptions lack details about the grips on the halves of the deck, but the illustrations provided by Maskelyne seem to suggest the palms-down “butt shuffle” grip, and Koschitz uses the term “butt-in”.
The anonymous book, The Whole Art and Mystery of Modern Gaming Fully Expos'd and Detected, 1726, p. 91, is often cited as containing the earliest description of the Faro Shuffle. This isn't correct. The book details a controlled shuffle, mixing cards one-by-one by dealing cards alternately, first from the top, then from the bottom, into a pile. The outcome of the shuffle (and the mathematics driving it) are markedly different than that of the faro Shuffle. While it isn't what we consider a faro shuffle, this mixing procedure was in use by dishonest faro dealers prior to the introduction of weave technique.
The original purpose of the faro shuffle was to gain an advantage at the game of faro. To understand its usefulness, it helps to understand the game it was used in. A simplified look at faro is to think of it similar to roulette: Players bet on a value of card and hope that it comes up. The croupier deals out two cards: one winner, and one loser. If the player bet on the winning card, he doubles his money; if he bet on the losing card, he loses his bet; if he bet on any other card, he neither wins nor loses. The crucial detail is that if two of the same value come out as the winning and losing cards (e.g., two kings), the dealer takes half of the player's bet on that card. This “doublet” or “split” is the main house advantage, and it's where the faro shuffle is used to unscrupulously stack the odds in the house's favor. By keeping track of specific cards dealt into the winning and losing piles, the dealer will position them at the same positions in their respective halves. When the two packets are perfectly woven together, the pairs will align next to each other. The next time the cards are dealt, there will be more doublets than random chance would provide, making more money for the house. A secondary – and bolder – use of the shuffle was to stack the deck to target players who consistently bet on the same card. The dealer would secretly get all the cards of that value in one half of the deck before weaving the cards together. This would position the cards to always fall in the same pile – the losing pile. For more details on the game of faro, see The New Pocket Hoyle, 1807, p. 139, Jonathan Harrington Green's An Exposure of the Arts and Miseries of Gambling, 1843, p. 165, the anonymous A Grand Exposé of the Science of Gambling, 1860, p. 1 of the 2010 edition, and The Official World Encyclopedia of Sports and Games, 1979, p. 158.
Persi Diaconis notes that S. Victor Innis was the first to publish the fact that eight out-shuffles bring a fifty-two-card pack back to its original order. See his Inner Secrets of Crooked Card Players, 1915, p. 13.
The use of a perfect (faro-like) shuffle to gather four Aces distributed in a sixteen-card packet was noted by “Dorian” in The Magic Wand, No. 7 No. 8, Apr. 1917, p. 122; “The 'Simplicitus' Four-Ace Trick”.