I'm assuming you know how to make a simple origami crane (don't worry, it's not too difficult). I used this site to learn how www.sadako.com/fold/folding.html
I started with 5 inch by 5 inch plain white printer paper. Anywhere from 4 to 6 inch paper squares should get the job done.
I recommend folding 5 cranes to start.