Basically, run the game in logging mode. Use the + and - keys to cycle through and find the texture you are looking for. Hit enter on a texture you want to change, this saves the texture to the hard drive. Then open it with your favorite photo editing software, I use gimp and make the changes you want. To upscale is never enough, you'll just see the same texture slightly smoother if you use a scaling algorithm (built into the upscale function). You need to go in and fix what you don't like: re-draw straight lines, use clone tool to eliminate bleeding, use smudge tool to smooth areas, and re-draw/paint details that can't be salvaged etc...
Once I have it cleaned up I like to add bump maps to areas that have unique textures. There is a plugin built into gimp for this and you can create and/or choose patterns and textures as the bump map. Tweak the settings to your liking. So if you look at Wrex's armor I added a Kevlar type bump map to the non-plated parts of the armor, a rough metallic bump to the plated areas, and a diamond pattern bump to the dark parts. It takes experimentation with the patterns and the bump map tool to get the desired look.
Then once the colored texture is to my liking, I like to generate a new normal map which will Incorporated all of the textures and tweaks I just created. There is an add-on for this in GIMP. Again it takes experimentation with the plug-in to find a desired look. Once I have generated a new normal map I like, I blend it (using layers and "grain merge" mode) with the original normal map. I use the original because it maintains all of the 3D data ( the depth and light angle that the developers captured from the 3D model), if I only used the one generated from my re-texture the result is very flat and characters don't "pop" (This is because it's generated from a 2D Texture and is missing the 3D data from the model). It took me months think of and get this technique down, but I like the results.
So in short you need to have or develop some photo editing skills, an eye for what you want, and the tools mentioned above to do it. Also, you need time, time, time :). The great thing about Gimp and TexMod is that they are free.
The sorting of textures is a pain. You need to make sure you copy all of the names of the textures you want in a pack into a TexMod.log file. Set up the directory just like I state in my tutorial on Moddb. The difference here is you go to "Package Build" in TexMod and select the log file and click "build", then name the .tpf appropriately. Voila you should be able to load the textures into the game and see how they look.
Be prepared to re-do everything again and again, as sometimes what looks great in 2D looks awful in game ;)