Michael Sacasas enlightens us:
Toilet paper, in case you’re wondering, was in use in China as early as the fourteenth century and it was made in 2? x 3? sheets. Everywhere else, and in China before then, people made use of what their environment offered. Leaves, mussel shells, corncobs were among the more common options. The Romans (what have they ever done for us!) used a sponge attached to the end of a stick and dipped in salt water. And yes, as you may have heard, in certain cultures the left hand was employed in the task of scatological hygiene, and in these cultures the left hand retains a certain stigma to this day.
Americans took a more literary route:
It has been claimed that the Sears and Roebuck catalog was also known as the "Rears and Sorebutt" catalog. The Farmer’s Almanac even came with a hole punched in it so that it could be hung and the pages torn off with ease. Toilet paper in its present form first appeared in 1857 thanks to Joseph Gayetty. It was thoughtfully moistened with aloe.