Questions that occur:
1) How long has this been happening? If not long, and you have restore points predating the issue, have you tried a
System Restore?
2) Does Search work in other user accounts?
3) Are you getting any error message when trying to search (i.e., 'Internet Security settings prevented...')?
4) Have you changed permissions on your system?
5) Do specified locations to index appear in Control Panel/Indexing Options?
Check this recent thread where some viable solutions have worked:
Search box in start menu does not work
Be sure to let us know if your issue continues or is resolved.
A good Search configuration and use tutorial for when you get it working:
Windows Search - Configure and Use
James