Hi, there is really no need to book a tour. We stayed in Krakow for a week last November and wanted to visit Auschwitz. There are loads of touts at the train station selling tours, but their prices are very high compared to doing it yourself.
We got on a train in Krakow ( Polish public transport is very cheap and reliable, though the trains can be very slow) which takes you to the town of Oswiecem, the main camp is about a 15 minute walk from there.
Be warned it is very busy, with lots of tour groups being led round, and I'm sure they are very informative, but I personally felt that going at your own pace, with time to reflect, was better.
We took a taxi from there to Birkenau, again very reasonable, that place is eerie, there was a group of Israeli schoolkids there which made it even more poignant.
Its something that I will never forget.
On a lighter note, agree with Albags about the saltmines, the ride back up to the surface in a miners cage was an experience!
Also try to visit Zakopane, couple of hours by coach from Krakow, again don't book a tour, just go to the coach station, its about a quarter of the price.