Pixel art can be done in any program that allows pixel-by-pixel drawing. MSPaint is probably the simplest and most direct, but higher-order editors can be used as well.
The thing to remember with trying to do pixel art inside of something like Photoshop (or Paint Shop Pro, or any of the others of this type) is that you need to turn off all of the fancy automated effects, especially anti-aliasing. That's the one thing that will kill pixel art.
To use Photoshop, you generally just need a single pixel brush/pen/pencil/whatever, with opacity and hardness settings to full 100%. Then, just go to town! (generally zoomed in to the level where you can see your work pixel-by-pixel)
Avoid vector work (this means that Flash is generally no good for this). Try to remain strictly raster.
Purists will also avoid using any of the pre-built shape drawing tools and any of the other gadgets, but if you have to use them (often, it's just a waste of time to try to pixel a perfect circle when the program will do it for you, even though most of these tools create vector elements), always make sure to refer to the rule above: turn off anti-aliasing, and make sure all hardness and opacity settings are cranked to full.
Along this line, another thing to remember is that it is best to work at the single-pixel level. If you do wish to work larger, and shrink it down later, remember to ensure that the resizing settings you select do not cause blurring of the final outcome. You want direct pixel resizing (most resizing in high-order editors automatically applies anti-aliasing effects... you don't want that) Another thing to keep in mind with this method is that you need to stick to a strict grid of squares, no matter what size you're working in. At the 1-to-1 pixel level, this is simple; there's no way to do anything but work within the grid of pixels. But if you're working at 200%, with a 2x2 tool, you need to make sure that you're placing each mark within a grid of 2x2 squares, and not half and half.
You want your drawing to remain looking like it was pixeled, not like it was done using brushes and filters...
Now, this is not to say that a good piece of pixel artwork can't be shaded to near-photographic quality, with smoothed, hand-anti-aliased lines and so forth, but the further you get along this route, the further it grows from looking like pixel art. This point is a matter of personal taste, though. Some pixelers strive for the highest-resolution, near-photo quality they can get, while many others prefer (almost religiously) to remain "primitive", to protect the "purity" of the art form.
Part of the "spirit" of pixel art is that it remains looking pixeled. Otherwise, why not just draw the image using all of the fancy effects and brushes?
But yeah, as long as you can set your program up to draw pixel-by-pixel, it's just as good as any other for making pixel art.
The final thing to remember is that JPG is no good for pixel art. The artifacting caused by JPG's lossy compression will blur and ruin pixel art (this effect is not as noticeable in normal images, but it simply wrecks pixel art). PNG and GIF are the best ways to go (BMP works, too, if you like overly huge filesizes : ) ). I prefer PNG, but unfortunately, the NG forums do not (yet?) accept the format, so GIF it has to be.
Note that I'm no expert in the field, so only take the above as some friendly advice from someone with some experience with this, and not as some sort of Pixel Artist Commandments, or something...lol
Anyways, here's another piece (this one from another game, one emulating the well-known puzzle game where you have to slide cars around to make a path for the target car to exit the lot. this game is not my own, but I did the artwork for the developer):