i'm by far one of the worst wallpaper designers on wincustomize.com but i'll at least put in my two cents for whatever good it is worth
i personally use adobe photoshop 6 a lot, i'm pretty sure i'm not the only one. it's solid and very expandible with plugins if you should need them or want them. i havent really ever done much with paintshop so i can't speak for it usability personally. i guess whatever you feel most comfortable with and that you can afford.
other useful tools depend on how much you really want to do. most of the higher end 3D apps like 3DSMax are expensive and a pain to figure out at first. other tools you may want or need depending on how far you want to go in terms of crazy designs.. to be honest, if you just intend to make wallpaper this is a very expensive way to go about it.. >
assuming you have all the tools you need, or want. what you need to do is really decide what you intend to make. Sometimes though I'll sit down to draw something and what comes out isn't what I planned on.. Like take Plasma1280.. I never intended it to look like it does, the thing took on a life of it's own. Sometimes those are the best too.
after you have your idea, just start trying to draw it with whatever image product(s) you have decided on. although sketching on paper is always fun. i find it more useful to sketch my ideas like they were going to be the final product, rather then using paper. unless the thing is very complex.
most of all, i've found it's unlikely that anything i ever draw will ever see the light of day.. in otherwords what i've done is just a hideous mess. for every one drawing of mine you might see.. there are 20 that you won't. so just keep practicing that's what's important. i've learned techniques quite by accident sometimes and go "ooh, cool!". so i guess the best advice is don't be discouraged if what you've done doesnt look very good.
Best of luck!
Alyssa - zSynchro