Basically, we can cache, but it has to be reset often, as we can't cache price data for too long. I'm sure we can do something about the stars though.
I would give a progress bar with semantics specific to what you are doing (step 3 of 5 instead of 60%), estimated time to completion, and a description of the current step (Submitting search request to Expedia... Filtering results... etc).
It can be accomplished a lot of ways, but will likely be more responsive if you push the data. The easiest way I have set up something like this has been node.js, redis pubsub, and socket.io. Requires some reading, but the end result is you can push messages through Redis from your app easily, it will work in all browsers, and you won't have to write very much glue code at all.