The levels are your story and express the plot; they are chapters in your novel told via the game mechanics. So, pay attention to each of them, especially the first ones, because that is the place where the player meets the game. The players should like the beginning to continue playing.
You can start planning the levels on paper, making different notes and sketches. Then it is better to switch to a more flexible tool. For example, it is good to use spreadsheets tools (Microsoft Excel or Calc from the OpenOffice.org package) to create a sketch of a level. That is unusual, but let's break stereotypes because spreadsheets can be very efficient: you can add various colors to cells, copy, paste, and cut them, move some sections of the level, and make some grouping operations. Moreover, you may find the way to save the spreadsheet document in a form that can be recognized by your game, so you will have not a sketch tool, but an improvised level editor!
The following is an example of the level sketched in the spreadsheet application:
Of course, a special level editor is better, especially if it has a test/preview option. This means that the editor should be based on your game engine. Try to make it practical, so that not only you but other people could use it too. Initially, all the level designers can be from your team, but then you can try to offer level creation features to a wider audience. Projects that let users generate content are always in fashion.