To change the skin of the UI you'll have to create/find images to use. The image file WoW uses for it's UI are .tga files. Take note that MS Paint can't open .tga's, you'll need something like Photoshop of Paintshop Pro to create and edit .tga files. You'll have to create/find images for each individual piece of UI that you want changed, reskinning the entire UI is a large undertaking as there are about 50 individual pieces to it.
There are a few ways to go about creating the actual images for each piece. You can create, relatively simple (but very nice and fairly detailed) images using something like Paintshop Pro. Or you could do what T.King does and actually render each UI piece seperately in a 3D rendering program like Maya, 3Dmax, GMAX or similair stuff.
Then, when you have images you like for the seperate UI pieces you have to code the UI so it is functional. This is done by way of XML files. While XML is a fairly simply language, it has many, many variables and can be overwhelming at first, but becomes easier as you learn everything.
As someone above suggested if you are really serious about undertaking a complete UI skin I recomend taking a look at T.King's work. Download one of his full custom skins and open up the files and look around. He won't be upset, or even care really, that you open up his files and check stuff out as long as you don't reuse his images or redistribute them without his permission. After you've taken a look at what's what, if you have any question the Author Forums on this site are a great font of UI-making knowledge and is a great place to start.
Good luck and I really hope to use some of your work someday
