my $self = bless ({}, ref ($class) || $class); # This is not necessarily wrong, but make sure that you understand exactly what it means.

$self->{'allowed'} = (); # This variable is not properly defined as a list.

my $size = $options{'size'} || 9; # This may not do what you want. If you use Perl 5.10 (you should!), consider using // instead of ||.

for (my $i = 1; $i <= $size; $i++) # This is OK, but it is C style, not Perl. Consider writing:
for my $i (1 .. $size) # This is more Perlish and more readable. It's a matter of taste.

$self->set_value(value => $value) if ($value > 0); # This may be it's correct for Sudoku, but what if $value is supposed to 0? Consider:
if (defined $value)

my ($self) = @_; # You should probably write:
my ($self) = shift; # Option 1.
my ($self) = $_[0]; # Option 2. The two options do a very similar thing, choose the one that suits you and make sure you understand what they mean.

$cells[$row] = (); # You probably want to write:
$cells[$row] = []; # Read the documents perllol and perlreftut in the standard Perl documentation. (If you're don't know where to find them, you can just Google these names :)