Looking at Perl Best Practices I would have to say the answer is that you should not quote them (unless necessary). I do not think TheDamian addresses this specifically but all of his "good" examples contain unquoted keys. For example, see "Keys and Indices" on page 14.

The closest he comes to explicitly covering this is under "Fat Commas" in the "Reserve => for pairs" section on pages 66 - 68. This quote particulalry stands out " [ The Fat Comma ] also removes the need to quote the key string . . . ." This is recommended because it reduces screen clutter and thus increases the readability of your code (see the "bad" example on page 67).

So, if you like the guidlines set forth in Perl Best Practices then the answer is to only quote hash keys when necessary.