American Wasteland: A Social and Cultural History of Excrement,1860-1920
By Daniel Max Gerling, B.A.; M.A. Dissertation Presented to the Faculty of the Graduate School of The University of Texas at Austin in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy The University of Texas at Austin:
Although Gayetty’s Medicated Paper, America’s first toilet paper, was
introduced in 1857, it was a luxury few Americans could afford.
Therefore, most outhouses were equipped with a corncob hanging by a string from the wall. And after the Sears Catalog became commonplace
in the 1890s, it was a staple in many outhouses for use as toilet
paper. Several photos from the early 19th century of the inside of
outhouses of tentimes feature scraps of newspaper or piles of rags.
Some also had buckets of lime to control the odor.
Since corn was originally cultivated only in the Western Hemisphere, it's likely that corncobs was something the European/American settlers adopted from the indengious peoples there. But the rags and newspapers mentioned were probably commonly used in Europe, and brought by the Europeans to the New World.
In the Boy Scouts, I was taught to used dried leaves when out in the woods on a hike, and that such was the practice of Native Americans, and presumably early American Settlers.
I also found a few references to the use of stones by Native Americans, but nothing I can cite as a reliable source.