El codigo que te han puesto es muy bueno, creas un formulario donde escribimos el nombre, supongamos que le das el name "busqueda", simplemente recojes por post y haces la consulta.
Código PHP:
$cadena = $_POST['busqueda'];
$query = "SELECT * FROM usuarios WHERE nombre LIKE '%".$cadena."%'":
$result = mysql_query($query);
//sigues con el resto