the paper I use is regular printer paper, but foil works really well (and looks cooler).
With this kind of design, smaller is usually better/neater looking -- but too small greats really difficult. My squares are 2 1/8 " on a side, b/c I took an 8 1/2 x 11, made a square and divided it into 16ths.
For more fun, try making a stellated octahedron w/ 16 pieces!!!
These make great holiday decorations, or gifts (I've made a few pair of earrings from foil-made ones).
Step 1: Precreasing
Just follow the pictures...
Step 2: Folding a unit
do this w/ 6 squares of the same size.