This isn’t about literally searching your install of Ubuntu, this is about searching the Internet for help. For example, if I search Google for Ubuntu games, I get a general mish mash. I get a Digg story on the Top 10 Ubuntu Linux Games. Better yet though, I can use a customized search just for Ubuntu.
Of the two I found, I prefer the customized Google Ubuntu search engine. While its honestly nothing specia (you can set up the same thing yourself), it is rather convenient. I liked the results I got from the custom search rather the broad search my first Googling gave me. The other option is the Ubuntu Search Engine from Ubuntux. Ubuntux gets props from me for what they do for FOSS and specifically all Ubuntu/Linux developers.