I don't claim to be a pixel art expert, nor would I try to push my knowledge on anyone, what I am trying to present here is what worked for me (a non artist). When I started my game Agartha, I never imagined in my life I'd be doing pixel art. My brother Mario, who does the music for Agartha, is a great artist but when it comes to doing pixel art, he never came through for me. I had the coding skills but I have absolutely no art talent, even now with Agartha, I feel I tapped into something that happens to work but it was out of mere luck that I would find something I'm satisfied with.
So what do I recommend to those who want to become pixel artists but stink when it comes to making any attempt? Start small, most games are made up of a small screen resolution. Super Mario for example is 160x120 maybe even smaller, but the player never notices this, it gets stretched by their television. A common size used by the Sega Genesis appears to be 320x240, this seems to be an ideal size for any 2D game screen. Next is determining the size of the sprites and tiles, sprites can be anywhere from 24x24 to 48 by 48, at least thats what I use for Agartha. The sprites I use commonly for Agartha are 48x48 while the smaller sprites are 24x24 and the tiles (that make up the level) tend to be 24x24. A question you may ask is, why such small sprites and tiles? The reason is the smaller the object you're working with, the easier it is come up with something your satisfied with. When designing a sprite you're going to use at least 4 different colors at the minimum. Super Mario for the NES only uses 4 colors (at least thats what I counted). Besides general colors for the sprite I'd also recommend a shadow and highlight.
A good way to get started with doing pixel art is to draw a small sphere with a solid color. Add a shadow to the lower right using a darker tone of the same color and a highlight (the part of where your light source reflects from) to the upper left, using a lighter tone of the base color. While drawing this sphere you should get familiar with Dithering. Dithering is creating a pattern from two colors, an example of this would be drawing a row consisting of a black pixel, then a white pixel, then a black pixel and so on. Dithering is a great way to make your sprite look like it has more colors then it actually has. The old Macintosh computers only had two colors; black and white, but to the untrained eye there appeared to be a grey. The grey was made from an illusion created by the black and white pixels, this can be applied to other colors as well.
My first sprites were based on the style I observed from Super Mario for NES, that seemed easy enough to do. The only problem was the sprites looked like something out of an Atari 2600 console, it seemed the Super Mario style was more difficult then I had originally thought.
Not only did Super Mario's style of pixel art not work but I felt I could do a little better. I began looking at 8-bit RPG's but I didn't find inspiration until I observed the character sprites from Final Fantasy 6. The Final Fantasy 6 sprites were similar to my sprites, being that they only used small dimensions and a small number of colors, but what made them different was the dark outlines. Dark outlines? you may ask, dark outlines consist of using a dark color to outline your sprite and it's features. After making this modification to my sprites I found a style I was satisfied with.
Now that I got sprite making out of the way I had another problem: making tiles. In a video game a level is made up of a pattern of tiles, even complex games like Ecco the Dolphin have levels made up of tiles. In Ecco the Dolphin the tiles range in size from 128x128, to as small as 32x32. Because the tiles are so large there is plenty of room for detail. Being I wasn't a pixel artist I had to go with something dramatically smaller; 24x24. My first attempt was with drawing rocks, I made a few pebbles and boulders but they looked awful. I grew frustrated with level design and I didn't find an edge until I walked away from the computer and returned to it with an idea that would change everything. I took my pebbles and boulders and jammed them together in their own 24x24 tile. The result was a great looking tile that I could use over and over for a level. I used this technique, using the same boulders and pebbles to make different patterns, I'd even flip the patterns in different directions to create even more patterns - I now had the tools needed to make a level.
The best technique to learning anything new is to mimic what you see and improve upon it. I observed many old school video games and I noticed some had graphics that I could do. You will need a good program for creating sprites, if I had one recommendation it would be GIMP. GIMP is great because it is free, it works under all operating systems and has many tools that could make any piece of crap look good. I don't recommend Photoshop, it's expensive, it's not worth pirating and it's slower.
If there is any advice I can give to those beginning pixel art it is; develop a style and make sure your level reflects that style! This means don't try to use images from other sources or artists, unless it matches up with what you have done. It's all about consistency and this is something new video game developers fail to observe. Also if your new to pixel art, start off with sprites that use small dimensions and observe examples from other video games. If you aren't too good at art, look at 8-bit video games and try to adapt their style, you'll find most of those games are extremely easy to out-gun.
For Further Reading and a Great Source on Sprite Design: Petesqbsite.com