This is always the hardest question to answer. Those of us who
do make wallpapers all start the same way..... with a new, blank document in Photoshop (or whatever program you use). The question you should be asking yourself is, what kind of wallpaper do I want to make?. If you know the type of thing you want to make, then you can look for tutorials on achieving it.
go to a good search engine, like this one > http://www.google.com and type in "Photoshop Tutorials", you will be amazed at the results you get. The good thing about tutorials is that you can make the kind of stuff you want to make while learning about the various tools in Photoshop.
This would be a good place to start for tutorials http://www.photoshoproadmap.com
I hope this helps.