Normally I am the last person you probably want to consult on art matters unless you want a clinical option but I reckon I can claim a reasonable amount of knowledge here, a reasonable amount of skill is a different matter. I will try to avoid making the distinction between spritework and animation for the moment as it is not a useful one in small projects. I will note animation is a massive timesink to do well.
Three schools of thought
1) Jump right in. You have probably played games all your lives and though that might mean you consider the N64 an old console (and if you were born when it was released in Aus I would be wishing you happy 16th birthday in about 2 weeks so that is not so bad) and you missed out on 16 bit and older at the time you have probably gone back or seen a lot of it. You might not know the names of the techniques but you can probably figure them out.
2) Traditional artistic progression. A lot of the art rules about drawing people and objects still apply. Though breaking them is quite important for a lot of sprite work (large heads and disproportionate things).
Still start with a stick figure and move sideways works well enough.
3) Emulate console progression. Kind of like 2) really but start with spectrum style, move to 8 bit, move to 16 bit and then factor in arcade niceties. Bonus is you will probably learn a lot if you take it seriously- most people will probably know Mario's moustache was a trick to avoid making a mouth (or at least so the story goes) but there are other nice things like Lemmings (
http://upload.wikimedia.org/wikipedia/en/a/a6/Lemming_animation.gif - reverse engineer what was done), prince of persia (well noted for rotoscoping) and doom (more on that in a moment).
4?) The cheating bastard methods. Twofold of vector images (modern street fighter is probably the most notable for this) and nearest neighbour shrinking/psuedo rotoscoping- doom was fairly noted for this where they would make clay models, scan them and turn them into sprites for enemies. 3d is increasingly used as well though it goes back a long way (SNES Donkey Kong being a good example though not really the earliest) and today stuff like NSMB on the DS uses 3d models all in hardware instead of sprites.
I would also suggest at least a couple of hours reading up on voxels.
I really also ought to mention when you say sprite are you going for actual restrictions in them like one working on the consoles might face and workaround techniques (palette swapping, composite sprites- legs on half and top half swaps out at will....) or are you going PC like where it just takes a bit more CPU, storage and memory and you can do anything? This comes into play first when people want to use gradients and multiply/darkening effects (I see it often enough when helping out with titlescreen hacks).
Software.... to each their own, I tend to be more on the editing/replacing front so the worst I have to do is regen a frame/create an intermediate if I am doing a sprite swap or something so I am probably not going to be much good on the ultra specialist $15000 a chair but does sprites, does sprite animation and does it all spectacularly software- good old Gimp, restricting myself by thinking what I can not do and using a few restrictions the program affords works well enough for me. If I were to start paying for something then
http://www.humanbalance.net/gale/us/ would be where I start though
http://aseprite.com/ (an open source rough equivalent) would probably catch my eye beforehand. As prices go up more things appear (
http://www.cosmigo.com/promotion/index.php first of all) but I am not sure what to say here as we have left my area of comfort.
Likewise though I called it a cheating bastard method plenty of game devs in antiquity and beyond use conventional image editors (
http://gbatemp.net/threads/once-you-see-it-classic-game-title-screens.326030/ ) and "spriteify" it when it comes to actually getting it done. If you want gifs I like
http://www.benetonsoftware.com/Beneton_Movie_GIF.php though the paid GraphicsGale does well enough here.
As I mentioned it for vector work I tend to use inkscape
http://inkscape.org/
More than any other art area though you will probably want to land yourself a drawing tablet for this. An entry level Wacom tablet seems to run about the price of a game, a proper one is a different matter (hundreds) but entry level should be good enough for the time being. I am not sure what exists on the "abuse a regular tablet as a remote control" front right now though it could be interesting.