David uses Photoshop, and other spriters that use it agree that it is a good tool. I understand the process to be generally that you start at 4x the intended size, aligning to pixel boundaries for near-verticals and near-horizontals, and then reducing; which is sort of a hybrid of painting and pixeling;
I use Paint.NET because it's simple, but also has layers, and a lot of times I borrow from existing Starfarer art for the greebling, especially when I want sprites to look like they belong with other Starfarer ships. My process for Nomads was to create outlines in Inkscape, because it has good alignment tools and can export to bitmaps via the clipboard easily and quickly, and then do the painting and detailing in Paint.NET.
Other than that, it really comes down to artistic eye, and attention to detail. There are a lot of pixeling techniques outlined at the pixelart community on DeviantArt that I used to frequent, so I would reccomend that as a potential resource.
Can't think of anything else ~