I made a tetrahedron. I chose to make this polyhedron because it has the fewest number of faces and I wanted to make something simple.
Step 1: Preparation
Determine size of face. I chose a 4" equilateral triangle, since i wanted my polyhedron to be small and regular. This created an end result that fit in my hand.
Then, draw paper template. Cut it out of paper.
Step 2: Cut Fabric
Lay paper template on fabric of choice (I used felt, but a sturdy cotton should do just as well. The shape may not hold as well if using a fabric of a lighter weight.) and trace AROUND paper template, leaving seam allowance (I used 1/4").
Then cut on traced lines.
Step 3: Sew
Sew three triangles together with 3 vertices at a point. Then sew the last one to the base of the tetrahedron, remembering to leave an inch or two unsewn so that you have room to turn it inside out.
Note: I used a serger because I made this to practice using the serger. It is unnecessary and silly to use the serger on felt, a fabric that will not fray. Do not use the serger for this project, unless you want the seams facing outward (in which case, skip turning it inside out), which I guess looks cool.
Step 4: Stuff
Carefully turn it inside out, and stuff with stuffing. I used some polyfill variant. Put enough so that the tetrahedron can sit on any side and still look like a tetrahedron, but not so much that it becomes bulbous and loses its shape.
Then handstitch the opening closed.
Step 5: Done
Now you can squish it at your leisure. It should also have a slight bounce, depending on what you used to stuff it, so you can throw it.