#1 - I would recommend either GIMP, or Paint.NET, try them both (both are free) and choose the one you like the most, I use Paint.NET.
#2 - UV mapping. After the model is finished you have to UV map it, UV mapping is the process of taking the model, and flattening it out.
After the model is unwrapped, you can add different colours to it, so it looks multi-textured, but really, it's all one 1 file.
There are lots of free programs that you can use to make models, Wings 3D, Anim8or, Blender. As well as payed ones, Milkshape, AC3D, 3ds Max (Note; the latter is a couple thousand dollars), personally, I use Anim8or (although, I do use Max at school)
There are also a few free programs for UV mapping, Wings 3D has it's own, and there's another free program called UV Mapper Classic, I would recommend it.