My suggestion: just turn it on and test it on a sandbox or developer org. Should become pretty clear.
Update: reading MarkPonds comment on behavior in VF, I would recommend to stick with the current pattern sfdcfox describes using sorted lists from keysets as iterators. The weird and incomplete documentation might be a hint that this isn't shipped as a big feature but more as warning for those who currently relay on the old in deterministic ordering (who ever this might be...). Critical updates typically come more with a risky flavor than with the aroma of a pure feature.
There isn't much more information available yet. I just saw this alert in the partner Community with some backgrounds:
Who is impacted by this?
Any partners using Apex code that exercises
order-dependent logic on unordered collections.
What is the change?
In anticipation of planned changes to Java Development Kit 8 (JDK8), Salesforce is changing the Apex implementation for unordered collections (maps and sets) to make the order of elements in those collections deterministic. With this update, the order of elements in maps and sets is the same every time your code is run again.
This update may cause a different iteration order for maps and sets than the current order. Once this change takes effect, any Apex code that exercises order-dependent logic on unordered collections can fail.
Why is this change happening?
The current underlying data type used by Apex for maps and sets is incompatible with upcoming changes being made to the Java Development Kit (JDK) for security and stability. The benefit of this update is that it makes Apex code more robust because the iteration order of unordered collections will always be the same.
What action do I need to take?
On March 24, 2015, this change will be released as a critical update in the application, which gives you control over testing and activating this change in your org. You can test and enable the change until your org is upgraded to the Summer ‘15 release*, at which point we will auto-activate any remaining orgs. Please see “Critical Updates Overview” in Salesforce Help to learn more about the critical update process.
During this period, you will need to update any Apex code or tests that rely on order-dependent logic. Prior to the auto-activation date, you can toggle between the current and new behaviors to support testing efforts.
*Currently scheduled for June 2015; date subject to change Where can I go for more information? For more information, please reference the release notes or the relevant Force.com Developer Guide topics on maps or sets. If you have further questions, please submit a case in the Partner Community.