cara, eu usaria assim,

<?php
$String = "Trocando os espacos por under lines ";
print(str_replace(' ','_',$String));
// retorna Trocando_os_espacos_por_under_lines_
?>

<?
//texto
$string = "alsdjalsd alsd__as djasdja";

//texto q vc procura
$buscar = "_";

//trocar por
$trocar = "";

$var = str_replace($trocar,$buscar,$string);
?>

Não se esqueça de utilizar a função trim($var) para retirar os espaços em branco da variável, evitando o erro do 1º exemplo. Que retorna:
Trocando_os_espacos_por_under_lines_ .

Uh, se considerar tabs e retornos de carro (é horrível esse termo, mas não lembrei em algo melhor par o enter)

ai não irá funcionar.

Dê uma caçada no http://www.phpclasses.org que lá tem umas classes boas de substituição bem completas. Não lembro de nenhuma de cabeça.

Mas se o que quiser é somente com espaços (imagino que quer renomear um arquivo de um site certo?) então a ideia é valida.

Mas tem também outras funcoes para manipular strings e urls bem interessante, dê uma olhada no manual no capítulo de funções de strings.

Isso resolve a questão dos outros tipos de espaços (tab, etc...), e substitui um ou mais espaços por um '_'.

$texto = preg_replace("/\s+/","_",$texto);

Sd's
Cau