Once you have a firm concept of what you want to draw in your mind, the formation of a piece of pixel art invariably begins with its outline.
BLACK is the colour traditionally used for lineart. You might like to try experimenting with other colours.
For smaller game sprites, this lineart is often most easily produced using the single-pixel-width, free draw tool (with help from line and other shape tools), often placing down a single pixel at a time.
For larger backgrounds, sprites or set-pieces, you may find it easier to scan hand-drawn art, or use a tablet.
In the case of backgrounds, it is often easier to build them up piece by piece, layer than layer, rather than as one combined piece. Breaking down the problem simplifies things, and editing object position is much simpler.
At first glance these outlines appear harsh and jagged, due to the square nature of pixels and their dark colour. Don't worry about this - things will get better later.
For game sprites, I find it preferrable to build them bulky, firmly packed and purposeful. Don't do any pose by halves - exagerate movements and don't let characters stand around limply. Keep your sprites interesting and energetic.
Remember, it will rarely look right first time round! Figure out where your lineart is flawed, and fix it until you are happy with it.
Take your time to get it right at this stage - mistakes will be harder to correct once you have started shading.
It is strongly advised that you edit every line down to a single pixel thickness, like so :
This is a boring chore at times, but it does improve the appearance of your sprite. Failure to put in this effort shows in the reduced quality of the final piece.