I personally feel it's better to apply online. A school won't hold either online or paper applications against you, but they typically prefer you to apply online, since it makes the process a little easier on them.
If you're using the Common App, the website is really easy to use, and the entire application and school-specific supplements are right there. It's convenient just to go to the website and knock some of it out at your leisure. It makes less paperwork for you, and you can submit applications to as many schools as you want simultaneously. Some colleges even waive the application fee if you apply online.
Even for schools that don't use the Common App (I applied to 12, 2 didn't), applying online was still a lot easier for many of the same reasons.
As far as teacher recs and such go, you print out the required forms and mail them in separately. My guidance counselor made 12 copies of everything (transcript, recs, resume, etc.) and we sent an envelope out to each school.