perldoc perldsc will give you lots of information how to deal with that kind of structures. It's not that hard.

Update: expanding more directly on you bulleted list:

is it possible to step through the hashref and return the data with some sort of magic/test to see what's there?

For the 1st part see perldsc. For the second part: ref

How can one tell if these keys would be returned in the same order every time from this (or similar) module?

There are modules that implement ordered hashes. But plain vanilla Perl hashes are unordered by design.

Is this type of data structure encountered other times, with other modules?
If this is just a one-off occurrence, perhaps it's not even worth bothering with figuring out how to do this.

This is a weird question in my perception. This kind of structure is the bread and butter of every day perl programming.