For many years in the late 1990's, we heard the idea of a "paperless environment" tossed about. Obviously, this never really came about, no matter how hard we've tried. Has it reduced the amount of paper? Sure. But it definitely has not eliminated paper completely.
One of the problems is that legislation was behind the electronic signature. Basically, for many years, you needed someone's physical signature, in case they came back and challenged that they actually signed things (let's say, for credit card bills, or dropping a class). Yes, there are plenty of holes in the idea of a real signature, but it's all we had. Nowadays, you've probably seen the electronic signature pads that are in place in a lot of areas - Target, many grocery stores, and other retailers have these, and they're considered just as legal.
Going forward, paperless is a good idea, but what if you have 20 years worth of paper records?
The thing that scares users is the idea of scanning all of these things in. For example, our school must have hundreds of thousands of pieces of paper that they keep around, and can you really entrust scanning documents and making sure something isn't lost to someone with little computer experience? Probably not. Do you want to pay someone experienced $50 an hour to do repetitive work? No, you don't want that either.
This has spawned a set of companies that will scan your documents for you and store them electronically. For example, there are sites such as Pixily - which will allow you to simply mail in documents. If you know someone with a small company, this is a site that might be really useful if they've got thousands of paper records just sitting all over the place. You mail them documents, and you get scanned copies, for a pretty low price.
There are more expensive and more comprehensive companies like Digital Documents as well, but this is something that would probably be overkill for a small office.
It may seen funny, but even in a smaller environment such as my college, there are rooms devoted to paper records that could be better used for other purposes - offices, classrooms, other storage, etc. Plus, in case of a flood or other natural disaster, paper records can fail. Converting them to electronic form will not only remove the need to store the originals - it will also allow you to use normal computerized backup systems to save those records for the future.
We're not paperless yet...perhaps someday we will be.