Also, OP, consider using constants so that you would not have to think about array order more than once. And create a hash that would store mapping from type of elements to perl comparison operators...

#!/usr/local/bin/perl

use warnings;
use strict;

use constant
  { NAME   => [ 0 , 'cmp' ]
  , NUMBER => [ 1 , '<=>' ]
  , CITY   => [ 2 , 'cmp' ]
  , STATE  => [ 3 , 'cmp' ]
  , ZIP    => [ 4 , '<=>' ] #  Assuming zip is a number
  } ;

my @customers =
  ( [ 'nye, bill','39','Somehere in Cali','Colombia','12345' ]
  , [ 'simpson, homer','36','Springfield', 'OR', '23456' ]
  , [ 'rubble, barney','31','Bedrock','cartoon location','33456' ]
  );

#  Get user input for sort order
my @criteria = (NAME , NUMBER , ZIP , STATE);

my $sort = make_sort( \@criteria );
my @sorted = sort $sort  @customers;

#my @control =
#  sort
#  {  $a->[NAME  ->[0]] cmp $b->[NAME  ->[0]]
#  || $a->[NUMBER->[0]] <=> $b->[NUMBER->[0]]
#  || $a->[ZIP   ->[0]] <=> $b->[ZIP   ->[0]]
#  || $a->[STATE ->[0]] cmp $b->[STATE ->[0]]
#  } @customers;

use Data::Dumper;
$Data::Dumper::Deepcopy = 1;
print Dumper( \@sorted
            #, \@control
            )
            ;

sub make_sort
{ my @how = @{ $_[0] };
  my $sort =
    join ' || '
      , map
          join( $_->[1]
              , q/ $a->[/ . $_->[0] . ']'
              , q/ $b->[/ . $_->[0] . ']'
              )
          , @how ; 
  return
    eval "sub { $sort ; }";
}
[download]

Above can be retrofitted for other similar structures.

Update, Feb 1, 2004: Above is another take of Fun with complex sorting... by Dave the davido.