Step 1: Supplies
Art supply stores (especially online versions) often carry wide rolls of paper. The ideal paper is very strong but very thin. Cotton content is usually a good thing for strength. Depending on what you're making transparency, prints or textures can enhance your design, so choose carefully.
Teacher supply stores often have big rolls of paper used for covering bulletin boards and similar applications. These can be cost effective, but do be aware that they will often be prone to fading and not made to last.
Restaurant supply stores carry butcher paper, and that can be a great material, too.
I used a 48 inch wide black paper made by Spectra Art: http://www.dickblick.com/products/spectra-artkraft-duo-finish-art-paper/
Step 2: Practice and Scale
This is a good time for very complicate forms, and for improvising in some extra detail folds. You'll probably be working 5x larger or more, so play around with some extras.
Unless you have a very sturdy paper or are willing to glue in extra supports (did you hear the origami purists gasp?) choosing a sturdy design with lots of layers is best. A paper crane will probably be really floppy and limp, whereas a heavily layered elephant will be more likely to stand up well.
When you have a model you like chosen and tested, you can use a bit of math to determine what size of finished model a piece of giant paper will result in. If a 6 inch square makes a 2 inch tall kitty, a 48 inch square will make a 16 inch tall kitty. If the final size is very important to you it's easy to calculate it this way.
Step 3: Cut the Paper
Unroll enough paper to fold it along the diagonal into a rough square area.
Fold on the diagonal, but it a bit further out.
Fold that in half, again on the diagonal, aligning the edge very accurately.
Fold it in half one more time.
Use something square to cut it all off neatly, then unfold your perfect square, ready to use!
Step 4: Fold the Giant Version
Fold this paper the same as the small, being sure to use a lot of care to align well. What would be a tiny error in normal paper is now a giant error.