The earliest description of this utility prop so far found is in Guyot's Nouvelles récréations mathématiques, Vol. 1, 1769, p. 57. The earliest discovered description of the change bag in English occurs in a book on mathematical amusements. Surrounded by genuine mathematical demonstrations, the Change Bag is described as a method to force a number in the anonymous Philosophical Amusements, 1797, p. 7.
Henry Hardin, in his column in Mahatma, Vol. 3 No. 2, Aug. 1899, p. 275, writes about “The Plush Bag”, a Change Bag with a handle, the form in which it has predominated to the present day. Hardin's article seems to imply that the prop was available, presumably from magic dealers, and he comments that it was “but little known” at the time of his writing. Also worth noting, perhaps, is “The Wonderful Velvet Bag” in W. H. J. Shaw's New Ideas in Magic, 1902, p. 30. This does not add any additional information, but unlike the Hardin write-up, it does include an illustration.