Just to be clear, I'm NOT talking about paint programs like photoshop or gimp or what have you... Any reccommendations? (Must be free software)
Have use the BlackSmith 3D suite in the past for a model of the Canadaman Halo mod... sample of the result at :
http://www.moddb.com/mods/halo-sins-of-the-prophets/images/new-ffg-ingame1#imagebox
The suite is not free but the blacksmith3D paint is free...
http://www.blacksmith3d.com/blacksmith3D-3d-paint-software.php
The work method is somehow different that with photoshop or gimp... you directly paint on the 3D model... segmenting and UV are made by the software... you don't need to take care of seam or other problem with 2D paint... back side are that the UV are not really optimised... and are a mess for modify them manually later !!!
In fact, you don't really paint but apply already existing textures... you can find a lot of texture reference on google image... try these link and you will understand what i mean : http://images.google.com/images?hl=nl&safe=off&um=1&sa=1&q=spaceship+texture&btnG=Zoeken&aq=f&oq=&start=0