How to make textures?

This guide is geared moreso towards creating textures for models, but many of the same principles apply.

https://polycount.com/discussion/73559/texturing-for-team-fortress-2-a-short-guide

There's also this presentation some Valve developers did in 2007 documenting the rendering techniques used in TF2. This might be a little out of scope here since most of the presentation is about model shading and the associated mathematics, but they do cover the methodology behind the texture design, and provide examples of influences for where they took their style from.
There's a video, a slideshow, and an extremely detailed paper documenting everything.

https://wiki.teamfortress.com/wiki/Illustrative_Rendering_in_Team_Fortress_2

Otherwise if you're persistent with asking around in the Discord server I'm sure someone would be around to help eventually. Getting textures right is largely trial and error.

As for programs, generally people use Adobe Photoshop.

https://gamebanana.com/tools/5353
https://www.deviantart.com/createvi/art/Dutchman-s-TF2-Brushes-389657011

Some photoshop brushes for tf2 texturing that I can't recommend enough. These can also be manually imported into pretty much any image creation program.

Are there any pre-made brush adaptations for paint.net?