Bazookao
vas a necesitar un toque de Ajax, o lo que es lo mismo
hacer llamados asincronos a la base de datos con javascript.
Aqui hay un tutorial que lo explica:
http://www.dynamicajax.com/fr/AJAX_S...1_290_312.html
tambien esta la opcion facil de usar jQuery, hechale un ojo a este plugin:
http://docs.jquery.com/Plugins/Autocomplete