This instructable will (hopefully) demonstrate how to make a stellated octahedron out of a single square of paper. You will need one square of paper.
I've added new pictures to make the process more clear.
Step 1: Sixteen Squares
Fold your square as seen in the picture to create 16 smaller squares within it.
Starting with the colored side up, fold in half, then fold the ends to the crease you made by folding in half. Do this in both directions.
Flip your paper over.
Step 2: Sixty-four Triangles
Make diagonal creases as shown in the picture(s), using the squares you just made as guides.
To do this, fold the diagonals of the whole square, then fold each corner to the corners of the three squares it fits with Leave the smallest triangles you make down.
Step 3: Collapse
Note: This is like folding a waterbomb base with the corners folded in.
Collapse the model as seen in the pictures so that it looks kind of like the profile of a diamond (The gem kind, and upside-down).
About the video: Green lines are mountain folds (pointed out towards you), red lines are valley folds (pointed away from you). I don't know what the .MOV format is, but I managed to open it in IrfanView, which is an awesome free program. Sorry, my camera has no sound.
The images with the blue backgrounds may be more useful than the older images.
Step 4: Tuck
Again, the pictures with blue backgrounds might be easier to follow.
Fold the point of one flap to the angled crease opposite it, then fold the tiny triangle back. Repeat for other 3 flaps.
Tuck the triangles visible under the triangles you just folded into the triangles you just folded.
Repeat with other three flaps.
About the videos:
P10103700 shows me folding to the creases marked in the first picture and folding the small triangle back along the crease that's already there as shown in the second.
P101072 shows me tucking one of the smaller triangles into the small triangle as shown in the fourth and fifth pictures.
Step 5: Inflate
Grab the model on both sides to separate the flaps and blow in the hole to inflate it.
Yes, we can all see sexual innuendo if we want to.
If blowing doesn't work, you can pull/squeeze it into its 3d shape.
Step 6: Poke and Pinch
Poke in the creases that popped out when you inflated the model to create the pointed shape. You may want to pinch the creases of the pyramids to help retain the shape.
The last 4 pictures are just so you can get a better idea of how the shape is formed.