lo que quieres hacer se puede, con el evento onkeypress y haciendo una pertición por medio de ajax al servidor. Pero ten en cuenta que realizará una consulta por cada tecla que rellenes en el formulario. No se si me explico
 
si introduces "maria" hará 5 consultas 1ª por "m", 2ª por "ma", 3ª por "mar",..,5ª por "maria". 
el codigo sería algo asi:
 BD:prueba
 TABLA: usuarios
                  -nombre
                  -apellido
index.php   
Código javascript
:
Ver original<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" 
   "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=iso-8859-1" />
<script type="text/javascript">
function objetoAjax(){
    var xmlhttp=false;
    try {
        xmlhttp = new ActiveXObject("Msxml2.XMLHTTP");
    } catch (e) {
        try {
           xmlhttp = new ActiveXObject("Microsoft.XMLHTTP");
        } catch (E) {
            xmlhttp = false;
    }
    }
 
    if (!xmlhttp && typeof XMLHttpRequest!='undefined') {
        xmlhttp = new XMLHttpRequest();
    }
    return xmlhttp;
}
 
function detectkey(evt,obj) {
keycode = (evt.keyCode==0) ? evt.which : evt.keyCode;
if (keycode!=8) {
    cadena=obj.value + String.fromCharCode(keycode);
    pagina='filtra.php?cadena='+cadena;
}else {
    obj.value="";
    pagina='filtra.php';
}
    divcontenido = document.getElementById('tabla_usuarios');
    ajax=objetoAjax();
    ajax.open("POST", pagina, true);
    ajax.onreadystatechange=function() {
      if (ajax.readyState==4) {
        divcontenido.innerHTML = ajax.responseText
      }
    }
    ajax.send(null);
}
</script>
</head>
<body>
 
<input type="text" name="nom" id="nom" value="" size="30" maxlength="30" onkeypress="detectkey(event,this)">
<br />
<div id="tabla_usuarios"></div>
</body>
</html>
  
  
filtra.php    
Código php:
Ver original<?PHP
if (isset($_REQUEST['cadena'])) {    $_REQUEST['cadena'];
   $query="SELECT nombre,apellido FROM usuarios WHERE (nombre like 'cadena%')";
}else $query="SELECT nombre,apellido FROM usuarios";
 
         or 
die ("No se puede conectar con el servidor"); 
         or 
die ("No se puede seleccionar la base de datos");      
?>
<TABLE>
<TBODY>
<TR>
<TH>Nombre</TH>
<TH>Apellido</TH>
</TR>
<?PHP
          echo "<TR>";
          echo "<TD>".$row['nombre']."</TD>";
          echo "<TD>".$row['apellido']."</TD>";
          echo "</TR>";
      }
?>
</TBODY>
</TABLE>
  
  
Pruebalo y me dices que lo he escrito pero no lo he ejecutado 
Saludos