Sorry for bad quality pictures!
Thanks to xavtek for the project cover.
Step 1: Materials
Make sure you have several square pieces of the same size. If you are gonna make the cube, you need 6 pieces. For the octahedron, you need 12, and 30 for the icosahedron.
Also make sure you have a lot of patience and free time.
Step 2: The Module
Start with a single piece of square paper.
Fold it in half, and then open it again. Fold both ends of the paper so they reach the middle of the square. Turn the paper and fold the sides as seen in the picture. Please note: you can fold either the left side or right side down, but you have to make all of the modules the same, or you are gonna have problems setting up. Ok, then fold the remaining edges up and down, so you get a folded square again, with these edges coming out. Turn it around again to fold it diagonally and your module is ready.
Repeat this step 6 times for the cube, 12 times for the stellated octahedron, ans 30 times for the stellated icosahedron. You can fold more if you want, in case you get some trouble making the whole thing.
Step 3: Setting Up
Take 3 modules and set them up as seen in the pictures.
Keep doing this, having in mind the form you want to achieve.
Check these links to have a deeper idea of what is a stellated icosahedron or octahedron:
Stellated Icosahedron on wikipedia
stellated octahedron on wikipedia
I don't have any strategy for setting up, I just keep going until it's finished.
Step 4: Colorful Patterns
In the picture you see a stellated octahedron set up with 4 different colors.
Step 5: Done!!!
Please comment on my first instructable. I couldn't leave notes on the images, please someone tell me how =]