You will need:
- A design or some pixel art
- Construction paper in appropriate colors
- A bright monitor
- Scissors, pen, tape
Optionally, large pieces of sturdy cardboard and some kind of glue to reinforce them. The Zelda sprites were simpler and I have better pictures, so I'll be using them to show you how this method works. I'll show you how general the method is by describing my octopus design at the end, which used the exact same steps as the sprites.
Step 1: Trace The Sprites
Open up your design in any program like mspaint where you can zoom in super close to the pixels. Adjust your zoom until their physical size on the monitor is the size you want it in real life, then lay a sheet of construction paper on the screen. Gently outline the shapes you'll need in that color with a pencil. When working with pixels, you really only need to mark corners - take serious measures to avoid putting too much pressure on your monitor in order to avoid damaging it. Try to arrange the pieces on a grid, almost as if you were playing tetris. The more shared edges, the less cuts and the easier it will be to ensure that the paper pixels are of consistent size. You can make barely-visible scribbles and then reconstruct the correct shape later. Of course keep in mind that simple arrangements (2 or 3 pixels in a group) don't need to be traced and can be drawn entirely with a ruler.
Remove the paper and draw a proper outline of all of the shapes with a straightedge. You'll want to be very strict about the sizes here. Each line segment must be identical in length, or your sprites will have unsightly gaps. This is much less important for more free-hand shapes like the octopus, but you still want things to line up.
NOTE that some colors may be too dark to trace through. If this is an issue, there is a way to circumvent it... but it will double your work. Simply trace through some white computer paper first, then use the resulting pieces as stencils to cut out the shapes in the color you actually want. I had to do this for all of the black parts in my sprites.