Lo que tienes que utilizar es ajax sin duda. Con una librería para evitar temas de incompatibilidades, como jQuery.
También hay algunas librerías para "autocomplete" por ahí, la mayoría basadas en jQuery.
Incluso sino son demasiadas puedes cargarlas todas con la web y hacer el autocompletado sin ajax con
http://jqueryui.com/autocomplete/
Sino una rápida búsqueda en google de ajax autocomplete te dará lo que buscas.