Any version of Photoshop after 5.0 will work fine. I do not reccomend any other program, as I don't use it, and therefore I can't give help (although others may use different programs and they may be able to help). I currently use Photoshop 7.0 myself.
The tutorial you should read first is:
http://www.ryandor.com/files/makingmaps.11.pdf
(right-click and Save As so you have a copy on your hard drive)
That has most of the basics you'll need to know.
After that, read through the FAQ forum for specific questions.
You can also do a search, and it may turn up a few other things too.
As for setting your map, you'll need to go into your client directory (where UO is installed) and BACKUP the files: map*.mul, statics*.mul, staidx*.mul, mapdif*.mul.
Then delete the mapdif*.mul files and put your new map0.mul, statics0.mul and staidx0.mul files in there as replacements. Make sure that the client is not running when you do this and also shut down any server you may be running.
-Ryandor
-Ryandor