First of all, i strongly join the people who recommended using Perl::Critic. It is an excellent to improve your style and avoid bugs.

You should also use Perl::Tidy.

Your naming, indentation and spacing style is mostly OK, but there are some lines which may be wrong.

Among them:

my $self = bless ({}, ref ($class) || $class); # This is not necessari
+ly 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, no
+t 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 thin
+g, choose the one that suits you and make sure you understand what th
+ey 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 :)
[download]

Another hint: If you only use integer values in your program, consider writing `use integer' in the beginning. It may improve performance. But compare your results with and without it.

Good luck!