You want to use Ajax Autocomplete. Check out the raw usage at http://wiki.script.aculo.us/ Or http://api.rubyonrails.org/classes/ActionView/Helpers/JavaScriptMacrosHelper.html#M000579
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.
Luke