How to populate an autocomplete using a web service? I want to populate a form field, an autocomplete widget, with values from an external REST web service without actually importing the data to my database first (on-the-fly).

How do I do that? Is there a module for that or do I need to create one myself?
There is not, as far as I can tell, a module that addresses this currently, though it wouldn't be terribly hard to build with some time on google.

But since you don't intend to harvest the responses from the API a javascript/jQuery solution may be the easiest route. Any time I build a new site I set up a module to house custom functionality in that is specific to the site, I suggest you throw together a .module and .info file and add your js that way, Drupal documentation on putting together a custom module is pretty extensive.

If this helps:

$("input#autofill").autocomplete({
        source: function (request, response) {
            var term = request.term;
            var restUrl = 'http://myRestService.com/search/'+term;

            $.getJSON(restUrl, function (data) {
                var items = [];
                $.each(data.results, function (key, val) {                          
                    var item = {
                        label: val.Label,
                        value: val.Value
                    };
                    items.push(item);
                });

                response(items);
            });
        }
    });