I used Magento 1.4.1 with Sample data ver.1.2.0. And when I used search module to search product, I reveived this line "Your search returns no results." And the solution is this:
Go to admin > System > Index Management.
Then, select all the indexes > Pick action is “Reindex data” > Press “Submit”.
Go to front-end and try again. Enjoy!