I'd recommend
The Photoshop Book For Digital Photographers. It goes from beginner to expert with very down-to-earth explanations. Definitely worth a look.
If you really want to dive in head-first (and have a few hundred bucks laying around), check out the Photoshop World conference. It's 4 or 5 days jam-packed with tutorials, classes, round-tables, and general fun. I went to one with a basic understanding of layers and knowing how to make selections and drag. When I came back, I was the go-to girl for Photoshop help. It's amazing how much you'll learn!