Also, when I paste that string into non-emacs things, as you can see, there is no underscore, but there is whitespace.

Look, puny mortal, are you questioning Emacs? The Holy Developers Environment written by God¹ Himself? If Emacs shows a red underscore, there is a red underscore; do not question Emacs by using software written by false gods² which cannot display red underscores. The correct way to replace a red underscore is:

   $str =~ s/_/-/;

Getting a red underscore in Emacs is easy - just hit the right 7 keys at once, and Emacs will start up the underscore wizard. You find the keys to hit in the info page (never use the manual page!). Inferior editors will not be able to do this.

¹Beard, long hair, open arms, must be a god.
²Shaven, has seen a haircutter recently, black turtleneck, cannot be a true god.