A puzzle such as the one illustrated was mentioned by Italian mathematician Luca Pacioli in his De Viribus Quantitatis (1496-1508). (I should point out that the caption underneath the illustrated text at this site belongs underneath the rings picture to its right.) Not long after Pacioli's mention, there is an apparent reference to it by Yang Shen (1488-1559): "Nowadays, we also have an object called nine linked rings. It’s made of brass or iron instead of jade. It’s a toy for women and children." The quotation is taken from this page. There have been attempts to place the puzzle in China even earlier: The oft-repeated story that it was invented by Hung Ming (181-234) belongs to Stewart Culin's Korean Games (1895) and is clearly not a serious possibility. Another suggestion that it was known in the Sung Dynasty (960-1279) belongs, I think, to Ch’ung‑En Yü's Chinese Ingenious Ring Puzzle Book (1958) or, more properly, to Yenna Wu's 1981 translation of it (neither of which I have seen), although V. Frederick Rickey suggests (perhaps erroneously) in this 2005 paper that it is from Stewart Culin. My take is that the Sung Dynasty connection is not, at present, credible.
Another European mention of the puzzle rings comes from Gerolamo Cardano's Latin De Subtilitate (~1550). John Wallis gives us a thorough description and illustration of the 'complicated rings', as well as its solution, in his Latin Algebra (1693). We find another picture of the rings in Jacques Ozanam's Récréations Mathématiques et Physiques (~1723). Hung Lou Meng's The Dream of the Red Chamber (~1750) mentions the "nine strung rings" puzzle (in H. Bencraft Joly's 1891 translation). From Johann Nikolaus Martius, by way of Johann Christian Wiegleb, we have Unterricht in der natürlichen Magie (1789), where it is chaptered Die Zauberkette oder das magische Ringspiel, complete with solution. Zhu Xiang Zhuren's Little Wisdoms appeared ~1821. Concurrently, William Clarke's treatment in The Boy's Own Book (1828) is shown here in an 1849 edition. He mentions the puzzle being called The Tiring Irons. The article was reprinted without provenance in The Magician's Own Book (1857), which is identical to The Book of 500 Curious Puzzles (1859).
A significant treatment of the puzzle arrived with a pamphlet written by Louis Agathon Gros: Théorie du Baguenodier (1872). David Singmaster was looking for this many years ago and I have not been able to find a copy either! Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr have recently named OEIS sequence A001511 the Gros sequence for this pamphlet's contribution.
A flurry of renewed interest rounds out the 1800s: The puzzle is in T. (which stands for what?) de Moulidars' Grande Encyclopédie des Jeux (1888), Le baguenaudier; Édouard Lucas' Récréations Mathématiques (1891), Le Jeu du Baguenaudier; W.W. Rouse Ball's Mathematical Recreations (1892), Chinese Rings; and Professor Hoffmann's Puzzles Old and New (1893), Cardan's Rings. Lucas footnotes (via O.-J. Broch) that in Norway the puzzle was used as a lock, a subsequently much-touted fiction. Rouse Ball (according to Singmaster) already noted that "It is said — though a priori the fact would have seemed very improbable — that Chinese rings are used in Norway to fasten the lids of boxes, ... I have never seen them employed for such purposes in any part of the country in which I have travelled." The objection, alas, was dropped from the third edition of Mathematical Recreations. Rouse Ball may have been the first to reference Cardan as paragraph 2 of Book 15, but I wonder if he was ignoring (or labeling as paragraph zero) the start of the De Subtilitate page (look for "Hoc instrumento ludus excogitatus mirae subtilitatis" near the bottom). Hoffmann talks of "the puzzling rings" and "the tiring irons" but makes 'Baguenaudier' feminine. He credits his solution to "an anonymous American writer" but it is clearly that of Clarke's Boys Own. Furthermore, his reference to another explanation in the Encyclopédie Méthodique des Jeux is likely meant to refer to that of Moulidars' Grande Encyclopédie.
Henry Ernest Dudeney has the puzzle as The Tiring Irons in Amusements in Mathematics (1917). Singmaster has noted that "the OED entry at Tiring-irons gives 5 quotations from the 17C: 1601, 1627, 1661, 1675, 1690." He also notes the variants Tyring or Tarrying Irons, and Tarriours. From Culin (1895) we have "Ryou-kaik-tjyo (Chinese, lau kák ch’á), or 'Delay guest instrument', is the name given to the familiar ring and bar puzzle which the Chinese call kau tsz' lin wán, or 'nine connected rings'." Pieter van Delft and Jack Botermans call it meleda in Creative Puzzles of the World (1978). More specifically: "Meleda first appeared in Europe in the mid-16th century and was described by the Italian mathematician Geronimo Cardano." Some readers of this sentence seem to have misinterpreted it to mean that the word goes back to Cardan. In fact, the introduction of meleda into English (it appears already in the puzzle sense in an 1835 Russian-French dictionary) is likely connected to the 1963 Halina Moss translation of Aleksandr Petrovich Domoryad's 1961 Russian Mathematical Games and Pastimes. In Puzzles Old & New (1986), Jerry Slocum and Jack Botermans go back to calling the puzzle Chinese Rings and otherwise repeat a lot of questionable gossip (the "Seal of Salomon" almost certainly refers to a different puzzle).
Martin Gardner's August 1972 column in Scientific American, The curious properties of the Gray code and how it can be used to solve puzzles, mentioned the Chinese rings. The article received a significant addendum in its reprinting as The Binary Gray Code in Knotted Doughnuts (1986) which mentions Sydney N. Afriat's The Ring of Linked Rings (1982), a book I have yet to read. Gardner suggested: "The Japanese became so intrigued by the puzzle in the 17th century that they wrote Haiku poems about it, and symbols of the linked rings appeared on heraldic emblems." These assertions beg for verification. Gardner also quotes the Oxford English Dictionary for this 1782 doggerel:
Have you not known a small machine
Which brazen rings environ,
In many a country chimney seen
Y-clep’d a tarring-iron?
There is a more complete version (transcript) attributed to S.S. (attributable to William Shenstone) in The Gentleman's Magazine Volume X (October 1740). The mention of the puzzle in chimneys is surely a bit of a mystery. Dudeney (1917) said that "it is said still to be found in obscure English villages (sometimes deposited in strange places, such as a church belfry)." What's up with that?