I am really interested in learning how to create sprites like this: http://thelessonlibrary.com/games/gsb/wallpapers.html.
I realize that creating something of this level will take a lot of learning and practice...but I am just completely fascinated by this and even if it takes me a year of working on it...I want to try.

So now for more specific questions:
1. What tools should I start to learn? Gimp? Inkscape? Blender? Do you think these sprites were created as 3D models and then rendered? Or were they just drawn in Photoshop/Gimp?
2. Is a good way to do this to sketch something up, scan it, trace into a layer in Gimp/Photoshop, and then play with different texturing?
3. Are there tutorials for people looking to work toward this? I have searched pretty extensively and most "sprite, 2D, gameart" tutorials I can find are either really basic and cartoony or like this:

Anyways, any help would be appreciated.
Thanks.

What is your skill level right now? If you don't have a solid foundation, I would suggest you start studying things like color theory, composition, light and shadow and all of the basic skills that will help you do art in any medium.
3D modeling is more like sculpture, and trying your hand at that could help.
Now for your specific questions:
1. At first glance, these ships look like they are pixel art and while you can certainly go that way, I then remembered the guy who made that game used the 3D in-game ship model to create a physical sculpture using a 3D printer. There are pluses and minuses to either, and experimentation would be the best way to find what works for you. http://www.positech.co.uk/gratuitousspacebattles/model/model.html

In theory you could do pixel art in something as readily available as the MS Paint program that comes with window, but you'll want to use something that has better layer managment, saving options, etc. like Photoshop or GIMP.
Stay away from vector based programs like Illustrator or Inkscape.

2. You can certainly sketch, scan and use that as a base for your final sprite, but you can't really just use a few filters or play with some textures and expect good results.

3. There are a ton of pixel art tutorials out there. Here's a good one: http://www.derekyu.com/?page_id=218
I'm not sure about making 3D models look like pixel art.

Thanks Hamsta!
I am pretty good at sketching(I've done portraits for people), and I have done some decent watercolor landscapes. So I guess I am not starting from square 1. I think I will start with that tutorial you showed me. I looked at your website and am very impressed. What software do you use for your artwork.

Thanks, andersonee.
I do my concept art in Photoshop or Painter for the most part. Sometimes I mix them, sometimes I use illustrator, entirely or just for logos and such.

Very Cool. Last question I promise: Do you use a tablet to draw? Like a Wacom? If so, which one do you use and why?

You can ask more, makes me feel appreciated. ;)

I use a Wacom Intuos 3 9x12.
Drawing with a stylus gives me much more control and a natural feel than a mouse.
Wacom because they have the best sensitivity and no batteries in the stylus, which helps ergonomically.
I started out with the original Graphire, but upgraded when I started college, and find it hard to go back to something like the school's Bamboo.

Size matters, the more tablet space you have, the more accurate it will be at translating your physical strokes to digital data. The sensitivity thing doesn't really make a huge difference, but tilt can be nice.
On the other hand, the larger tablets aren't as easily transportable.