The paths needed are displayed in a dull yellw text on the model page where you download the models, such as "grunt.blp" in the unzipped folder would need the path "units\orc\grunt\grunt.blp" after you import it into your map's import archive. There is a link to the tutorial for it on every model page. I suggest you read it carefully, for it any of the paths are wrong, the model will not work.
As for programs, your can create skins using Adobe Photoshop (adobe.com) or paintshop pro. models with Discreet 3D max (Discreet.com) or Gmax. You will also need several other tools, such as MPQ extracotr and a file converter, which you can download off this site in the tools section.
-VGsatomi