I want to convert a localtime date like so... I would appreciate any suggestions as to the most efficient and readable way to do this.

If by "efficient" you mean that you have a large number of these to translate, and that you really want to roll your own instead of using one of the several decent (but sometimes bloated) data manipulation packages, consider doing a hash lookup. Pre-generate a mapping like

  my %date_convert = (
    ...
    'Dec 29' => '04-12-29',
    ...
  );
[download]

  my $day_re = '(?:Mon|Tue|...|Sun)';
  my $mon_re = '(?:Jan|Feb|...|Dec)';
  my $time_re = '\d\d:\d\d:\d\d';

  $text =~ s/$day_re ($mon_re \d+) ($time_re)/$date_convert{$1} . "_" 
+. $2/ge;
[download]

You didn't show us where the year comes in, so that's an open issue you'd need to deal with.

Pregenerating the conversion hash is left as an exercise.