Teaching children to write w/o paper:
Magic slate can be adapted to classroom use. And unlike dry-erase boards (also possible), they're very cheap; a kid who goes through one a week (damaged or lost) may still be ahead of paper use in costs.
I suspect paper will be around for a long time--while digital devices are more economical in the long run, there won't be any immediate rush to supply them to people living in poverty now, who can afford paper (some paper, anyway) but can't make the jump to computers or PDAs, especially not for every member of the family. And on the technological side, DRM and proprietary software issues are going to continue to be a stumbling block for the ease of sharing that's involved in paper. (And then there's the copyright mess. You can hand someone a book, or hand it around to a group, and say "look at page 37." We don't have a digital way to do the same--they each wind up with a copy, rather than the "original" changing hands.)
That said, I think Steve's mostly right--we need to eliminate paper as the backbone of information exchange. I think it'll remain for art purposes, and for certain kinds of archiving (but not most archiving), and for personal sentimental activity (letter-writing's not going to vanish, but it could become a rare affectation rather than a business standard), and for children's activities (which may fall under "art purposes").
And you can put a notepad of paper in your winter cabin, and it still works four years later, even if the power is out. It'll be a *long* time before we can say that about any common electronic device; the cheap, solar-powered laptop is quite a while away. And while computer files can be annotated, signed, attached to each other, and marked "IMPORTANT!!", it's not always simple or quick to do so, and the different types of files mean everyone needs different methods to do these things that are easy to do with paper. Making electronic files as convenient as paper (or almost as convenient, with their own advantages, like searchability) is a long way off.
But "a long way off" doesn't mean "never." And we
cannot treat paper like it's an infinite resource--it isn't. One of the biggest problems in economic evaluations of methods and resources is the assumption that "raw materials"--trees, oil, rocks, water--are free; they only cost what it takes you in tools & labor to fetch them. There's no cost in the item itself, and its destruction is not counted as a loss.
The only cost the producer in tools & labor--but the tree milled for paper can't be milled again tomorrow, or next year. Nor the year after. And recycling, while admirable, is a shrinking resource pool; we lose some every time.