From Force.com documentation, you'll learn that every record there is a change to one of the following fields on Opportunity: Amount, StageName, CloseDate, Probability, or ForecastCategory. However it's not obvious to see how a stage change (or any change) is recorded (expressed in records). I eventually figured out that two time fields on the OpportunityHistory records are the key:
The time when this change happened
The time this record becomes history (the time when a new OpportunityHistory record following this one is generated)
So for instance, if you need to figure out what the previous stage was for a particular stage, find the OpportunityHistory record with the stage name first. From that record use the CreatedDate and locate a record with the exact value in its SystemModStamp. The stage name in that record would be the previous stage.
What's on the built-in Opportunity History report looks like values derived from the OpportunityHistory object instead of values coming directly from it.