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.
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.