Сначала urldecode строка поиска, а затем замените пробелы подчеркиванием. E.g.:
$str = "this%20is%20the%search%20term";
$decoded = urldecode($str);
$final = str_replace(' ', '_', $decoded);
Вы можете сделать то же самое с регулярным выражением, используя preg_replace
только более надежно, поскольку вам может потребоваться удалить несколько последовательных пробелов:
$str = "this%20is%20the%search%20term";
$decoded = urldecode($str);
$final = preg_replace("/\s+/", "_", $decoded);