For instance, wouldso would Time passes about changing www.example.com/search/mark+twain with www.example.com/search/mark_twain ?

The shape to look appears like this:

<form role="search" method="get" id="searchform" action="<?php echo home_url('/'); ?>">
  <label class="visuallyhidden" for="s"><?php _e('Search for:', 'roots'); ?></label>
  <input type="text" value="" name="s" id="s" placeholder="<?php _e('Search Courses/Material'); ?> ">
  <input type="submit" id="searchsubmit" value="<?php echo attribute_escape(__('Search')); ?>" class="button">
</form>

I am less than sure how you are by using this or where exactly you are by using their query, but you can always use string replace:

str_replace('+','_',$query)

This is the best solution I'm able to give with this particular vague an issue.

PHP Manual

For jquery (which wordpress utilizes) you could do this something similar to:

$('#sear form').submit(function(){ $(this).val($(this).val().replace(' ','_')); });

I believe that's correct. I am not where I'm able to check it out, however it should work.