Gimp is pretty decent graphic editor ;) you could also get yourself something older for beginings, personaly I bought Paint shop Pro 8.10 long time ago for reasonable price, it's pretty good for starters, quite easy and nowadays it's cheap ;)
as for textures, I usually draw basic shapes with vector pen over old texture, just to know what should be where (make sure you resised old texture to the size of new) when you're done with drawing basic shapes and lines on the hull just select new layer of vector lines andrse there copy them over to new clean map. From this point you just have to make new aztec patterns and draw everything you like on your new texture. Of course there are some much more efficient techniques but this is what worked for me from the begining ;)