After making several adjustments to an image I clicked the little icon in the history palette to compare to the original. I selected part of the image and noticed that the entire history palette cleared to show the step that I had just done. I tried using ctrl+alt+z but it would only undo one step. So my question is how do I undo to get to the step before, where all my adjustments are there?
Okay, you say you clicked on "the little icon" in the history palette. I'm assuming you mean that box at the top of the palette. That box is a snapshot of the initial state of the document. Once you close and reopen the document, all states and snapshots from the last working session are cleared from the palette. But, if you saved the document before closing, when you open it the next time you'll see that the top snapshot now represents the saved state.
Each time you apply a change to an image, the new state of that image is added to the palette (as you know). If you click on one of those states and then continue to work on your document, all the states below the one you clicked on will be discarded. That's what happened when you clicked on that top state (the initial state) and then continued to work (you selected part of the image). Clicking that top snapshot is like clicking on any other state listed on the palette. The reason the states are dimmed, by the way, is so you can see what will be discarded if you continue to work.
After you made that selection, if you had done a keyboard undo (ctrl + z) you would have seen all the states return. Instead, you used ctrl + alt + z which moves you backward within the states (ctrl + shift + z moves you forward). But since you now had only the one state (the selection) you couldn't move backward.
This explanation won't help get your adjustments back but I hope it will give you a better understanding of the History palette. You could also read about the History palette using "Photoshop Help" found in the Help menu.