Something like this?

package StringObject;

use strict;
use warnings;

use overload q{""} => \&to_string;

sub new {
  my ($class, $string) = @_;
  return bless \$string, $class;
}

sub s {
  my ($self, $match, $substitute) = @_;
  $$self =~ s/$match/$substitute/;
  return $self;
}

sub to_string {
  my ($self) = @_;
  return $$self;
}

1;
[download]

Quick inspection tests:

use strict;
use warnings;

use StringObject;

my $s1 = StringObject->new("the boy walked the dog");
print $s1, "\n";

$s1->s('walked', 'fed')->s('boy', 'girl')->s('dog', 'Audrey II');
print $s1, "\n";

exit;
[download]

You'd probably want to overload the other stringy functions (comparisons, concat) as well to make the semantics consistent.

As written, this won't handle backreferences in the replacement string. There are probably other limitations. I personally don't see a lot of benefits to this substitution chaining idiom in the first place, but I thought it might be fun to show an example of blessing something other than a hashref.

        $perlmonks{seattlejohn} = 'John Clyman';