I am in the process of writing an article about this very thing, actually... that's not helpful to you right this second, though.
Paper and pencil are best when starting off. To be very good, you have to practice a lot and that's easiest to do the old fashioned way. Even if you aren't planning on being a professional artist, it's a really good idea to draft everything multiple times on paper before committing to a design. You can even scan or take a picture of the final version to use as a base for your sprites.
Photoshop is good if you can get it, but GIMP is free and not very different in terms of capabilities these days. Inkscape I believe is the vector equivalent of GIMP: http://inkscape.org/. I would Inkscape and GIMP and see which one you like better.
The original FFII is pixel art, but that version looks like they made large raster versions and scaled them down. It's definitely not Vector art, although if you're just starting that might be easier to work with if you're willing to have a pretty different style. Here's a pretty good tutorial on getting art done fast (raster): http://www.gamedev.net/page/resources/_/creative/visual-arts/better-programmer-art-r2594.
I just got this book last week: http://www.amazon.com/Drawing-Basics-Video-Game-Art/dp/0823098478/ref=sr_1_1?ie=UTF8&qid=1363745212&sr=8-1&keywords=drawing+game+art. I think it's probably as good an introduction to drawing as any, although I think any book or tutorial is inherently limited since getting better depends completely on you actually practicing. It's a good reference, anyway.
Good luck! I'll let you know when I finish my article, you sound exactly like my target audience!