Hi Humalla, I haven't used PrintShop Deluxe, so I can't comment on it, but you will find that most people who are creating wallpapers are using Photoshop or PaintShop Pro.
Photoshop is the industry standard for graphics, but is quite expensive. PaintShop Pro is a lot cheaper and many people prefer it's interface to Photoshop's.
You can get a high end graphics program for free, it's called "The Gimp", and I have heard people say that it can achieve anything that Photoshop can, but when I tried it I found it a little confusing.
In the end, it usually comes down to how you start. If you start with Photoshop, you will always find that program easier, and the same goes for the others that I mentioned.
Personally, I use Photoshop, I can't fault it. But I have also tried PaintShop Pro, The Gimp, Fireworks, Bryce3D, 3DStudioMax, and many others, so just give them a try and see which one you feel comfortable with.
If you want to see what I manage to put together using just Photoshop, click here: https://www.wincustomize.com/skins.asp?AuthorID=194
I hope this has helped you.