For the purposes of these tutorials I am going to recommend one sprite editor : Graphics Gale, a fantastic free art package tailored towards pixel art which you can download here.
At first glance it may seem a little overwhelming, but it has every feature that I find useful: right-click pipette, easily accessable RGB sliders, an easily customisable palette, customisable hotkeys, layers, an animation viewer - the list goes on and on.
It really is a fantastic package, clearly designed with pixel artists in mind and it's hard to believe that it's free! It is receiving frequent version updates too.
Previously I had been using the Picture Editor in Clickteam's The Games Factory.
I found that the Frame Area and easily manipulatable object system make TGF most useful for storing and displaying pixel art, as well as drawing it.
Plus you can make 2D sprite games with them! They are well worth a look - they're not free but the prices are reasonable and they're a nice, simple way to get into games creation.
( MMF is their newest package, but it's pixel-pushing features are an annoyance to anyone looking to sprite in it. )
Tools you do not need :
1) Overpowered, expensive programs like Photoshop are not required, nor would I recommend using them if you had them. Use of features like blurring, filters, paintbrush tools and various other special effects will most often only damage your work and distort your style and I would strongly advise you not to spoil your art with them.
2) Microsoft Paint. It's rubbish - it has to be or MS would probably be facing lawsuits from various art-package companies for anti-competitive behaviour. Graphics Gale does everything Paint does and much, much more.