for (`locate $ARGV[0]`) {
  chop;
  -M and $f{$_}=($stat _)[9];
}
for $x (sort { $f{$a} <=> $f{$b} } keys %f) {
  printf "%s $x\n", scalar localtime($f{$x});
}
[download]

Broken down:

for $y (`locate $ARGV[0]`) {

## Run the system command locate, and send it the first 
## argument that was sent to the script. This will 
## return a list of lines (files), which gets stored into $_
## (because we did not give the for loop a variable)

  chop;

## We need to chop the newline off for the following 
## tests to work. With no argument, it chops $_

  -M and $f{$_}=(stat _)[9];

## -M returns the last modification time. With no argument, 
## it checks $_. We do this because locate may not return 
## a valid file. Perl actually does a stat behind the 
## scenes to get this info, and saves it away. We use the 
## 'and' to only do the next part of the statement if 
## -M returns something.
## (stat _)[9] - the underscore tells perl not to check 
## the file again, but to use the same information it 
## saved when it made the last check (which was -M)
## Stat returns a list, but we only want the 10th 
## element (in position 9, count from 0) which is the 
## modification date (similar to -M). We put this 
## time into the hash %f, using the filename (which is 
## still set as $_ from before) as a key.
}
## That's it, now the next line of locate's output is 
## parsed, until we are done.

for $x (sort { $f{$a} <=> $f{$b} } keys %f) {

## This says to sort all the keys of the hash %f, 
## which are the names of the file. We use a custom 
## sort by comparing the values of the hash, which 
## are the modification times. $a and $b are special 
## variables perl uses inside sort blocks, and the 
## spaceship operator <=> allows us to compare 
## the times numerically. This sorted list is then 
## passed to the for loop, with $x receiving the 
## keys of %f in the newly sorted order.

  printf "%s $x\n", scalar localtime($f{$x});

## We print it out. No particular reason to use printf - 
## I just happen to like it. The scalar and localtime 
## converts the value stored in $f{$x} (the modification 
## time) into something prettier to read. (the time is 
## stored internally as a 32-bit number, i.e. 958740893 
## which is not very pretty at all.)
}
[download]

Hope that helped. I know that this is probably really basic to most people (even the original poster) but somebody may get some use out of my verbosity. :)