I started off with 8x8 and Oryx's sprites to learn people shapes from. I worked on that basis for some time, making small adjustments to his sprites, or drawing new ones from scratch.
For Ludum Dare last month, I made three sprites myself at 16x16 scale. They don't look great, but they worked just fine:
http://www.ludumdare.com/compo/wp-content/compo2/201083/12174-shot0.png
The only snag here is some people hate pixel art. All I can say is that it's really worth starting here even if you don't like it. The small scope means there's not that many possible combinations of pixels in an 8x8 space. You don't get much choice, which means you focus more on each pixel.
Second thing is to use a palette. Only use six colours. Or twelve. Or two. Just pick one and stick to it. Choose off a site like http://www.colourlovers.com so you get one picked with someone who has a sense of colour (I don't). Things immediately start to look better once this happens.
Well it wasn't really planned but I just made this which I'm fairly proud of since it's my first creation that isn't a simple console application.
I'm an electro house nut. This just dropped 2 hours ago and it's what I'm currently listening to while coding : https://soundcloud.com/shreddie-mercury/shreddie-mercurys-1-hour