I'd second rjray's comment on flexibility. One key to productive Perl OO programming, IMO, is not to become bound by constraints other OO languages impose on you.

In the case of your search method, consider the fact that Perl lets you build hybrid methods that work as either instance (object) or class (static) methods. I know this is another one that drives OO purists wild, but I often find it useful. In the case of a search method, the possible application might be to either search within a row or across the entire set. Such a dual purpose method would look something like this:

sub search
{
    my $invocant = shift;

    if (ref($invocant))
    {
        $invocant->_set_search();
    }
    else
    {
        $invocant->_instance_search();
    }
}
[download]

As you advance down the Perl OO path, take a look at ties and closures -- 2 Perl constructs that give you OO possibilities many other OO languages don't offer.