I started using Photoshop probably a dozen years ago. There weren’t a lot of tutorials on the internet so I had to figure most of it out on my own. This caused some bad habits, but it also helped me develop very good problem solving skills. If I were to do it over, I would definitely learn the basics from a reliable source and mix that with self teaching.
One of the things I usually recommend people do is open up a photo and then press every single button, use every single filter, and one by one see what they do. Play around. Don’t worry about making anything worthwhile. Just push buttons and have a good time.
As for the more structured learning, I highly recommend signing up for lynda.com. They have a photoshop essentials course that you can finish in a weekend and have a pretty solid understanding of the program.
If you want to learn photoshop from more of an artist’s perspective, you might try out Bert Monroy’s Pixel Perfect series. He is a photo-realist who creates everything from scratch in photoshop.
If you want high quality tutorials on how to create special effects I would check out Planet Photoshop. All the tutorials are created by professionals and give you reliable, accurate information.
And if there is ever anything specific you wish to learn, usually you can just do a google search and add “photoshop tutorial” to the end. Not every tutorial will be wonderful. But usually they give you clues on how to achieve the effect you want.