Microsoft Paint (MS Paint)
Although I haven't used it in a long time, I can strongly recommend it, as it has all the basic tools needed to create even the biggest and most complex Pixel Art masterpieces. In fact, some prefer to use this because of it's usually minimal interface, it can be less daunting as a program with fewer buttons and options and more forward in making Pixel Art. The program should support transparency, although it does lack the ability for animation frames to be strung together and also lacks layers and colour/contrast adjustment sliders. Basically a simple and solid option for those with a Windows OS, and for free.
Another free art program that can be found here: [link]. I don't personally have any experience with it, but I can direct you to this article here which details what you need to do to set up the program for working with pixels -> GIMP for Pixel Art: Shortcuts, Setup and Tips. A good alternative for those who don't want to use Photoshop or Paint, but more something in between.
Perhaps one of the most versatile arts programs around at the moment, and one that I have a lot of experience with, is Photoshop, although it's not cheap and therefore many may prefer to use MSPaint despite having less features. This program has layers, colour sliders and curves adjustments, custom brush settings (that you can even use to your advantage in pixelling although not in the way you might think) and the colour picker has a handy hue spectrum running down the side as well as hex values and all the other values you could possibly want for any chosen colour. It's certainly not necessary to have all these features for Pixel Art, but it can save time or make the process more enjoyable and less tedious, depending on your workflow and methods.
I don't personally have any experience in using this one either but I hear a lot of Pixel Artists who claim to use it. The program can be found here: [link] and might prove a good alternative if you aren't a fan of the more well known programs.
"As someone who works with Graphicsgale, I can highly recommend it. The program is lightweight, the colourpicking / palette is easy to work with and the overall interface is uncluttered and simple. Furthermore, once you learn to work with the tools (colour-replacer = handiest tool ever), you can get icons done in under an hour, I've found. The only thing to keep in mind is that the free version doesn't support .gif- and .ico-files, but you can always use a program such as GIMP to animate and convert files." - `Hardrockangel
Another lesser known but useful program, I haven't used it myself but it can be a little easier to come by than Photoshop, and contains features beyond those that Paint has, but never quite reaches the same level as what Photoshop does, another good one for those who want something in the middle, but can still be expensive depending on whether you get the basic package or the bigger one.
Another one I haven't used myself, but sounds like a fairly solid and easy choice with more features than plain MS Paint, can be found here: www.getpaint.net/download.html. Very easy for beginners to use.
A program I haven't used myself, but has abilities regarding size compression and .gif file animation which would make it very handy for sprite makers and other game graphics.
Easy Paint Tool SAI
Suggested to me as another option for Pixel Art, I have experience in it but only a little and not for Pixel Art, but I think it could be useful those who prefer it to Photoshop already and thus already familiar with the tools.
The Pencil Tool (sometimes known as the "Binary" Tool)
The single most important and necessary tool, although it might go by slightly different names in different programs, this is the one that is a single pixel big when set to 1px in size and does not create a smooth line when drawing. The pencil tool is what you will use for more than half of your pieces, and if you use Photoshop, you can use the custom brush settings to set dithering patterns to save time. This tool does not create auto AA and therefore is entirely within the Pixel Art definition. As seen in the image, it can sometimes be hidden behind the Brush Tool, so make sure you have the right one.
As seen here in Photoshop (and potentially other similar programs), you actually also have the ability to change the shape of the Pencil/Binary tool, as well as opacity etc. Whilst you may want to stay clear of the opacity option at least until you are experienced with Pixel Art (as some traditionalists will exclude varied transparency as being viable in Pixel Art at all), the size and shape options are one of the lesser known advantages of Pixel Art in more advanced programs like Photoshop. I personally make use of them by using the scattering options and to create pre-made sections of checkerboard and other stages of dithering, which can then be placed into larger sections to save time.
One of my Pixel "brush" shape sets can be downloaded here: [link]
The Paintbucket/Solid Fill Tool
This is also within the bounds of Pixel Art's definition because it allows you to place a great many pixels in one area that would have looked the same had you spent hours meticulously setting out each them one at a time. This needs to be set so that it does not create auto AA although most of the time it shouldn't be a problem. It can also sometime be hidden behind the Gradient Tool, which is one of the biggest no no tools in Pixel Art, so ensure you are using the right one, there is really never a time I would say that the Gradient Tool should be used in Pixel Art, using it makes the piece instantly a Mixed Media piece.
The Line Tool
This is similar to the role of the paintbucket/solid fill tool, in that it simply helps you to place pixels in the same way you would have done one at a time, only quicker, only this time in a straight line. Holding shift helps keep the line straight especially for long lines (may not work for programs other than Photoshop).
Here we have the difference between a Brush line and a Pixel line, see the greyish pixels on the side of the first line? Those are automatic anti-alisasing pixels, and those are not a part of Pixel Art. In Pixel Art, you must apply those in between colour pixels yourself or "manually", otherwise they are outside the direct control of the artist. More on AA in further sections.
Although these are not always available depending on the program you use, it can be really good practice when making any art to have a sketch layer in a different colour underneath the layer where you work out and refine the details of the final piece. It also allows you to make changes that you can turn on and off to see the difference it makes to the overall image and allows you to keep separate pieces apart so you can easily animate them later. Image Source: [link]
Not available in all programs, although the Photoshop Animation or Timeline panel is very versatile and will serve your animating needs well. You can add frames, change the seconds for each of those frames, loop them or choose the number of loops before stopping. Image Source here: [link]
Opacity and Transparency
However your program is supporting it, make sure it can, because nothing spoils a piece quicker than an unnecessary blank background colour when it could have been made transparent. You can also look at using semi-transparent, yet still hand placed pixels which can be too much for some more traditional pixel artists but when used in moderation, can make the medium a little bit easier for those who just do it as a hobby etc. Beware that this adds to the colour count quite a bit and therefore some traditional Pixel sites may reject the piece for using a more modern technique. Not all programs may have the same pattern to indicate transparency, but the most commonly known white and grey checker pattern is from Photoshop.
The Selection Tools
Don't be afraid to break out the polygonal or freeform lasso tools and pull pieces apart and move them around, it can be a great way to restructure a piece, allowing you to pixel in the gaps to form a new image. You can also use a variety of other selection tools depending on what is available in your program, such as the elliptical tool for circles and ovals.