Perl Best Practices recommends Readonly. While constants with use constant are replaced at compile time, Readonly variables are normal variables, just set read-only.
The problem with use constant is that the constants are actual functions which don't interpolate in strings!

I recently needed the line feed ("\012") as constant (Note: "\n" is platform dependent!).
Compare:

use Readonly;
Readonly $NL => "\012";
[...]
print FILE "header1${NL}header2${NL}";


use constant NL => "\012";
[...]
print FILE "header1" . NL . "header2" . NL;
[download]

The speed penalty for Readonly is not meaningful in my case. However if you have large calculations which only dependent on constants, maybe inside a loop, then use constant is better because perl can optimise it at compile time.