This is a very broad question but I'll try and answer it anyway.
If this is not a learning exercise, I would recommend a plugin. Personally, I feel Mirasvit's Sphinx Search is very well written. You can learn from it and it does the job really well.
If this is a learning exercise then I recommend you spend some time improving your javascript through something like Codeschool.
In this instance, you would need a module with a controller to fire search terms at via ajax. The frontend javascript will observe the input box, and if more than 3 characters have been entered (or another suitable minimum) and another character is not entered within about 0.3 seconds, you should send off the current input to your newly created controller. The controller will return a json array of results for you to render on the frontend.
Magento actually has a built-in search, but it only lists previously searched terms, which is a bit rubbish imo. Might be good for reference though.