make sure that texture size is uniform across whole model, if you use 3ds max for example, before I do paint stuff I apply Box mapping modifier (UVW map) with size 32x32x32 for 256x256 textures, then I work with individual regions but typically I do not modify uv mapping sizes so final result looks happy
Initially it was random, I didn't know where to start with. And my way of doing it is a lot of UV manipulations.
start with box mapping like I proposed above, assign different materials to regions of the mesh, then fine map if required
