Step 1: Paper mache a balloon
I ended up using two balloons, so if the balloon color changes, that's why. One popped while I was taking a break.
Good instructions for paper mache-ing can be found herehere
Cooking the paste really works- I never did that when I was a kid, but things worked. Cooking the paste works BETTER.