I just messed around with it, and occasionally read some good tutorials. But mostly everything was done on instinct.
I would say that the best way is to focus on whatever you are interested in and everything else will flow from that. I started by wanting to color my pictures that I drew and from reading tutorials about that subject I learned about a lot of other stuff. Every time I wanted to do something new with Photoshop I would read tutorials on that subject and then learn a lot more in the process.
I started learning it while I was studying at university and have stuck with it since. I used to use Paintshop Pro before but found photoshop much more powerful and better for what I wanted to do. I found that tutorials helped me to learn more of the features available and occasionally I still do some when I have some spare time.
Books, I would go get lesson books from the library and go trough them and do all the lessons I didn’t know and go get another book and go through it. I think Photoshop Wow was one of my favorite books I learned a lot about filters and styles from that one.
Very nice questions ... I go in my old memories when I had started my first photoshop layout. I learned photoshop from my friend, it was version 4. On that time I just played with it. I browsed the photoshop help pages because on that time the internet surfing dial-up connection was very costly. I gone through some books, tutorials, friends. Now I am a photoshop expert, but I can't forgot my old days to learn it. Thanks to my friends and the tutorial sites.