First of all I came up with a really rough concept level design on a scrap of paper. Some tweaks were needed, but this concept contains the basic ideas for puzzle mechanics within the level design.
After I was satisfied with the level design, I planned it out a little more accurately on an A4 piece of squared paper. Graph paper has too many squares. In fact it is worth getting hold of squared paper that is as feint as possible, so that there is more contrast with your drawn design.
This step helps to ensure that the player character can make certain jumps up to platforms, and across gaps. You don’t want to player to find it either impossible or nearly impossible to access certain areas, unless that is intentionally part of the level design.
The draft level was adjusted in places on squared paper, then tested in the game engine, playing with the character to ensure that the various areas were the right height and widths etc. This squared paper version was then photocopied for use as a template when drawing the final level.
The final level was drawn using tracing paper, masked to a photocopy of the squared level drawing, so that there was an accurate guide for where the platforms, walls and ceilings should be placed.
The drawing was done starting at the top-right of the image, across and downwards, to minimise smudging. The rough details were placed with 2B pencil, and then filled in with extra detail over the course of the drawing.