I would start them out with lists, arrays, and simple constructs like foreach. Keep your examples concise and avoid anything that looks magical, or you will reinforce whatever stereotypes they have heard about perl golfing, and they will focus on the trees and miss the forest.

An example for foreach

# Basic example
my $sum = 0;
foreach my $number (1,2,3,4,5) {
  $sum = $sum + $number;
}

# A little better
foreach my $number (1..5) {
  $sum += $number;
}

# Probably shouldn't show this one
$sum += $_ for (1..5);
[download]

I would stay away from showing them map or grep initially unless you're dealing with someone with lisp experience.