I'm not sure if you saw merlyn's correction to my mistake, so if not, please use this code instead:

use strict;

my %map = (
   S => 0, M => 1, L => 2, Xl => 3
);

my @sorted = 
   map { $_->[0] } sort {
      $a->[1] <=> $b->[1] or
      $a->[2] cmp $b->[2]
   } map {
      /^(\w+:\s+(\w+),\s+\w+:\s+(\w+))$/ ?
         [$1, $map{$2}, $3] : ()
   } <DATA>;

print join("\n", @sorted);

__DATA__
size: L, color: White
size: M, color: Orange
size: M, color: White
size: M, color: White
size: S, color: Orange
size: S, color: White
size: Xl, color: Orange
size: Xl, color: White
size: Xl, color: White
[download]