- paper (ideally construction or other thick paper)
It should take about 10 minutes.
Step 1: Cut a Strip Off Paper
It isn't important how wide the piece is, but you want to get the long edges reasonable parallel, especially at the ends so the widths line up for the next step.
Step 2: Prep to Join the Narrow Edges Together
Cutting the end this way will
a) insure you tape the strip together right, and
b) make the connecting section stiffer, providing something similar to a "scarf joint" in woodworking.
Step 3: Tape the Ends Together
Hold the piece with the tape side up, and hold the other end on the other side of it. Flip over one end so the diagonal edges line up. Put the two ends as close together as possible and stick the loose end on the tape.
Add another piece of tape on the other side.
Step 4: Now What?
To show it really only has one side, put a pencil on a spot anywhere along the strip and keep drawing in one direction. You will end up where you started. Now that couldn't be if it had two sides, right?
There is more fun to be had if you now cut along the line you just drew, because you will not end up with two strips.
For more info, check out the entry for Mobius Strip on Wikipedia.
Some of Escher's drawings are also based on this concept.