Seems that since the Oct 20th update and using iOS 5 it saves your history now! I enter the first letter in the blank address bar and up pops all the places I've been. This must be a bug because I don't remember it saving anything before the last update.
If you have not updated it yet, I'd hold off. I've deleted it and downloaded the other free private browser (blue icon) but that one is annoying with all their recurring ads popping up.
These types of issues are probably a good reason to not have apps automatically update on their own.