As far as I can see, the problem isn't the tilde so much as the unescaped character just before the tilde. It's the same as your separator. If you use a slightly different syntax for the search and replace, you can do the transformation without issue.

~/perl/monks$ cat test_tilde.pl 
#!/usr/bin/perl
use warnings;
use strict;

my $test = "This is a test
of a replacement 
string, really (example.com) 
and truly."; 

print $test, "\n";

$test =~ s|example\.com|12\.23\.56\.78\/\~example|g;

print $test, "\n";
[download]

The output is:

~/perl/monks$ ./test_tilde.pl 
This is a test
of a replacement 
string, really (example.com) 
and truly.
This is a test
of a replacement 
string, really (12.23.56.78/~example) 
and truly.
[download]