To make a maze you will need:
graph paper
sharp pencil
functioning brain :P
The pics seen above the steps aren't necessarily the finished product.

Step 1: Mini-maze

Feature 1: Mini-maze
This is essentially a maze inside another maze. You don't want to make it too big, I'd say 10x10 squares is the max if you're using A4 paper. To make this Instructable I used online graph paper: http://www.garrettbartley.com/graphpaper.html
You start by outlining the border of the mini-maze.

Step 2: Spiral Box

Feature 2: Spiral box
It's a spiral with 2 open ends. Pretty simple once you see the pics. The openings need to be diagonally across from each other or it won't work.

Step 3: Modified Spiral Box

Feature 3: Modified spiral box
This is a spiral box with 4 open ends. Minimum 4x4 squares needed. You can also divide the feature into 2, as shown in the 3rd pic.

Step 4: Tunnels

Feature 4: Tunnels
A tunnel is a chain of squares that is separated from the rest of the maze. They can have a few openings if needed.

Step 5: Complex Dead Ends and Walls

Feature 5: Walls

To create a complex dead end, you first need to make a wall with one opening. Try not to make it obvious, so anyone who is doing your maze does not see it and falls into your trap.