If you can, try to take some Photoshop classes in your area. It's not the quickest route, but it's definitely the best route.
As far as books go, pretty much anything at a local bookstore would be good. Try to find a book that covers all aspects of Photoshop, not just one geared toward photo manipulation, vectors, or other specifics. For really basic stuff, you can read the manual that comes with Photoshop - it has some pretty valuable information in it. Tutorial sites are alright, but it's similar to the books - find a tutorial that covers all of Photoshop, not just a certain effect.
I'll be on the lookout for Photoshop books though. If I find any good ones, I'll keep you posted. =]