Pretty much practice, practice and practice (and have patience). There really isn't much more to say. It is a good idea to be able to draw good images on paper though, because it also helps you becoming more skillful with proportions and such, and you will inevitably pass that onto your graphics.

Right -- its practice, practice, practice, as well learning about how the old masters did it, and often a good dose of color theory (either formal or intuitive). You can get the latter two from the internet if you care to look, but you'd have to deal with the first the old-fashioned way.

Having a pixel-art program helps, especially for artwork using a limited color palette. I like Cosmigo Promotion, but there are others like GraphicsGale, and you can configure programs like photoshop, the Gimp, or Paint.NET for that kind of workflow if you know how (google it). By default, most popular graphics packages today that aren't explicitly pixel-oriented are set up for photo editing or larger-format, high-color, high-DPI digital painting, which isn't suited to pixel work; you'll have to reconfigure them before they're useful.

Echoing what was said above: takes lots of practice. However, with modern technology, there's room to cheat it a bit if you're good with hand-drawn work.

If you can make something like that with hand-drawing, either scan it at a lower resolution or scan with a higher resolution and reduce the size (probably without any kind of interpolation). Even then, you'll need some manual pixel art skills, especially if you want to achieve dithering the way they did it. You'll also need to limit your color palette.

Based on the screen-shot, it looks like the images were hand-drawn, scanned, and manually colored and shaded in the computer.

Actually, I think you are right. It seems like I remember reading somewhere that this indeed was the way capcom used to do the old "High-rez" sprites like this, classic Street Fighter 2, etc...

And I echo the other statements, practice tends to be the key. Cheating helps if it can get acceptable results. I manage to get quicker and better results using 3d pre-rendered sprites, but I can't get the beautiful pixel art results that way, rather "just" acceptable art for many situations.