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, 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.

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.