Overload is handled by "magic", and there are a number of perlapi functions which handle it properly, for instance sv_catsv. If you are manipulating strings by accessing the SvPVX directly, then the overloading won't kick in, but if you use sv_catsv, it will work.

Here's an extremely verbose version of "hello_world.plx" which illustrates the point:

package World;
use strict;
use warnings;

use overload '""' => sub { "world" };

sub new { bless {}, __PACKAGE__ }

package main;
use strict;
use warnings;

use Inline C => <<'END_C';

void
magical_concat(SV *a, SV *b) {
    sv_catsv(a, b);
}

END_C

my $greeting = "Hello, ";
my $world = World->new;
magical_concat($greeting, $world);
$greeting .= ".\n";

print $greeting;
[download]

perlapi functions that handle magic properly say so in the docs. I'd check out the source code for sv_catsv if you're looking for samples.