This bothered me for about 15 minutes until I found the solution online. Whilst building a site with Magento 1.4 (installed with no sample data), I added a product to test the system. However, when I tested the search feature, it returned no results whatsoever. I tried entering META keywords (which turned out to be on the wrong track entirely) and double-checked that the ‘Visibility’ option under Catalog/Manage Products was set to “Catalog, Search”.
The solution turned out to be this: Reindex Data
In the Admin Panel, go to System/Index Management. Select All items and then click ‘Submit’ next to ‘Actions: Reindex Data’. That should do the trick.