Traditional newsprint was mostly, if not completely, wood pulp, with little or no rag content. But, yes, cellulose.
I don't know too much about paper layering, but I know the preferred binder for making cardboard, as well as papier mâché, is starch. Methyl cellulose might be appropriate as well, as it would also size the paper. I don't think either is harmful to the environment, though the process for making methyl cellulose might be. On the other hand, with the right mild solvent to encourage the paper layers to bind, you may not need an adhesive at all, though in that case I doubt the printing would be preserved like you see in the video.