I've only used it a little, but this module seems to do exactly what is required if you require a hash to keep its order.
This module requires Perl 5.6.1; in a project that has to run on 5.005 I've used Tie::Hash::Indexed instead, but the interface this module has for assigning data while tieing is nicer.
My only reason for not giving it 5 stars is cos I'm not keen on the name. Putting it in the Tie::Hash::* namespace would have been preferable. Also many modules have a verb as the second part of their name, so when I first saw "Tie::InsertOrderHash" my thought was that it would insert something; I didn't immediately grasp that "InsertOrder" is a truncation of "insertion order". So I think Tie::Hash::InsertionOrder or just Tie::Hash::Ordered would be a better name.