Which script are you using? I'm assuming jQueryUI. This is referenced in your page?
From jQueryUI API:
When a string is used, the Autocomplete plugin expects that string to point to a URL resource that will return JSON data. It can be on the same host or on a different one (must provide JSONP). The Autocomplete plugin does not filter the results, instead a query string is added with a term field, which the server-side script should use for filtering the results. For example, if the source option is set to "http://example.com" and the user types foo, a GET request would be made to http://example.com?term=foo. The data itself can be in the same format as the local data described above.
You have to be careful with ajax calls, as you may end up making a call for every character typed. However, if this is what you need there is a good repo on GitHub - Twitter Typeahead / Bloodhound (http://twitter.github.io/typeahead.js/examples/)- I've used this myself to good effect. You can set it so that it only starts searching after a certain number of chars have been entered (e.g. 3).
Instead of setting search.php as your source, you will need to set your source as a function with an ajax call to search.php.
Not necessarily true. We use jQuery UI for our search autocomplete here on DaniWeb, and do it just as he is. jQuery UI passes in the term parameter in a POST request to Search.php, which just needs to return a JSON array of results making the assumption that $_POST['term'] exists.