You get to your lovely painting program, you get the image you want with size 512 x 512, then convert it to *.blp via Warcraft III Viewer and import it as let's say "Environment\Sky\FelwoodSky\FelwoodSky.blp". This will replace the Felwood default sky. Notice that you cannot add extra skies, so, if you want custom ones, you must replace pre-existing ones.