For some reason I have never gotten a good deal on kayak but maybe it's just me. Expedia usually works best when I'm booking trips.
The earlier you book from your interview datr the better most the time. If you book 2 interviews on the east coast near each other you can fly to one destination then bolt bus or mega bus to the next destination. I think they only go to major cities but it's like 12 bucks to go from DC to New York round trip sometimes. Seriously great deal.
Cheapest places to stay I would recommend airbnb.com again. Basically people rent out rooms in their houses. It can be as low as 20 bucks a night. With it being an interview trip though I would stress location and personally I would only stay at houses other people have reviewed. Like I said in another thread, you wouldn't want to be robbed right before an interview