Months go by and Google Reader still doesn't have a search feature. We tried to add search using Google Co-op, but you have to manually synchronize your subscriptions and wait until Google indexes the pages before being able to search them.
Now that Google Reader can store data offline using Google Gears, Raul Ochoa built a Greasemonkey script that lets you search the most recent 2000 posts, assuming they're properly synchronized. "At this moment the search is performed over the same database table used by Google Reader, in this table you can't use Full-Text Searches, so a simple/poor database query with like is being used."
This Google Gears + Greasemonkey solution is not perfect: the script tries to match the exact phrase, the search results are sorted by date, they could be formatted better and you have to manually synchronize the data by switching between the online/offline modes.
Assuming you have Firefox, Google Gears and Greasemonkey, here's the link to the script.
Update (Sept. 2007): Google Reader added search.