If the usual use case of your module looks like this:

use YourModule;
my $obj = YourModule->new();
my @result = $obj->search($params)
[download]

Then it's useful to offer ->search as a class method.

If however there are a few parameters to ->new() or some other state information is added between the calls to new and search then I wouldn't go through all the trouble of making these informations available as extra parameters to a class method search.

So don't go through the trouble of changing your interface because you read somewhere that it might be better that way. Only do that if you understand the concept, and you're convinced that it's actually better.