Which program are you using ?
I would suggest using gimp. It's a photoshop clone, just as good (for our purposes) and totally free, open source namely.
On top of that, there's a dds-plugin available for gimp. So you can just load those texture file into the graphics program and edit them right away, without some conversion by an additional program beforehand.
I'll give you the links first:
http://www.gimp.org
http://nifelheim.dyndns.org/~cocidius/dds/ the dds plugin.
If you wanted to add a tower insignia, you could just load some texture file for the desired sub type into gimp. Better make a dedicated directory for all you works and don't edit the files in the game folders right away.
The path to the tower textures would be [sh4 install]\data\textures\tnormal\tex\NSS_GatoTower_T01.dds for instance.
One problem is, that is it not obvious where to put your changes as those texture files are only flat files and sh4 knows which areas to pick for texturizing which parts of a 3d model. But there is no description for us which areas within a texture are used for what.
Using a submarine body texture is a bit easier because the shape of the hull comes out clear in the texture file.
As you wrote you already looked into such a texture file. If you load one with already a conning tower emblem in it (from some modder created skin) then you see, where to put an emblem in the texture file (for the according sub type at least) to show up correctly in the game. Positioning can be a bit of playing around.
For instance, I wanted to edit the *upper* side of the fore depth rudders of a sargo class. It was quite hard to find which spot in the texture file was actually responsable for the colour of the depth rudders. So I colorized the sub skin all in rainbow colours and looked where the colours went in the game. I show you what I mean:
The texture with many coloured rectangles
and how it turned out in the game
That way you can learn where to put stuff in the texture file and where it is gonna show up on your actual submarine. This is not as big a problem for the conning towers because they lack the detail of the 3d model of the subs hull.
These are the most important things. The rest is just basic (or sometimes good) knowledge of your preferred graphics program.
Gimp and Photoshop both have the ability to let you draw in different layers. So when you load a texture into gimp, this will be the background layer. You can then create a new, transparent and empty layer for adding additional effects or details to the already existing skin without having to mess up the actual texture. Because layers can be switched on and off, moved, deleted or hidden. So they keep your work organized.
If you're about to draw shapes onto a texture, the path tool (in gimp) might become your best friend. For adding rust or weathered effects use different brush types and sizes and set the brushes to low opacity when drawing.
I know, there are just some very rough tips, more of an overview so far. The work with layers, brushes and paths are very basic stuff using graphic programs as gimp or photoshop and there are many tutorials around to help you with those aspects in general.
If you wanted to, I could also give you more of a step by step tutorial in adding a tower emblem rather than this list of tips like here.
And at last: just starting an playing around a bit makes you often learn the most.
Let me know if this was any helpful or if I should go more into detail somewhere.
So far, i.