sub n {
    $_[0] =~ m#^(\d+)-(\d+)-(\d+)(.*)#;
    sprintf( "%02d%02d%02d%s",$3,$1,$2,$4 );
}
my @line = sort {n($a) cmp n($b)} <DATA>;
print @line;
__DATA__
1-22-03 somedata_somedata
1-23-03 wwwwwwwwwww
1-22-03 sssssssssssss
2-3-03 aaaaaaaaaaaa
1-3-03 sdddddd
2-3-03 ddddddddddddd
1-22-03 eeeeeeeeeee
2-3-03 hhhhhhhhh
1-3-03 kkkkkkkkkkkkkkk
2-3-03 llllllllllllllll
[download]

Not the fastest way to do this, as the normalization routine is called multiple times for each element. But it should do the trick, I think.

Liz

Update:
Broquaint's solution calls the normalization only once for each element, and is thus less CPU intensive. But will use a lot more memory because of the the intermediate array that is built. YMMV.