Some count parchment as the earliest "paper" -- others, papyrus

China is historically credited as the first place where paper as we know it was made, in approximately 250 B.C.  Earliest fibers were taken from old rags, hemp robe and old fishing nets.

Painting from 1790 depicts papermakers in China.  Two men use a large mold to form sheets.  A press removes excess water.  Finally, the water is set on a heated panel to dry. 

Gummer, Arnold E., Paper by Kids, Dillon Press, New York, 1980, Fig. 9-1.