If there is precisely ONE underscore in the requested URL, the job is simple:
Check whether the underscore needs to be escaped or not before using this code.
RewriteRule ^([^_]+)_(.*)$ http://www.example.com/$1-$2 [R=301,L]
For two underscores, it's:
RewriteRule ^([^_]+)_([^_]+)_(.*)$ http://www.example.com/$1-$2-$3 [R=301,L]
If it's always TWO, you only need one rule.
If it could be one OR two underscores, you need both rules, and processing time increases for every request arriving at the server.
Once it gets to "many" underscores it's time for a completely different approach.
In that case, use .htaccess to rewrite requests with underscores to a special processing script using PHP or whatever your favourite language is.
RewriteRule ^([^_]+)_ /special-script.php [L]
This special script then does all the processing using regular expressions and issues the redirect header.
This special code is only invoked when requests have underscores and therefore does not significantly slow down all of the other page, image, script and stylesheet requests.