There is a good tutorial here at
http://world-editor-tutorials.thehel...t/tilesets.php
I used it to replace "building cliffs" and a few others in my map. I used gimp and several layers, like cutting some regions, selecting by color, then applying filters and merging the layers, etc.
Cliff tiles are stored in a different way than normal tiles, but that link explains it in detail.
I used Wacraft3Viewer to convert to/from blp/tga, but there are other ways to convert...