hostelworld.com it's aimed more at the back-packing student end of the travel market, but you can often get single or double rooms, most european hostels are mixed rooms so if you're traveling with someone and not fussed about sharing a room with other people but want to be together then you should be fine.
The wife and I booked through hostel world when we went to Poland, stayed in Warsaw for a weekend, which we felt was enough to see the old city, then went down to Krakow where we stayed for a week.
if you wanted to see Austwitz, don't bother with the organised trips, you can just get a bus there, buy tickets at the gate and join a tour - take food and water.
Would recommend getting the lonely planet guide to Poland, very useful for city plans and lists of places to eat etc.