You want to use Ajax Autocomplete.
Check out the raw usage at http://wiki.script.aculo.us/
In your model, make it acts_as_ferret with the appropriate fields.
In your controller use find_by_contents to get the list of possible
contacts using the search string
I can provide code examples if you want, but this should be enough to
point you in the right direction anyway.