I heard that KDE has this great thing called "Nepomuk" for searching files (both by name and by contents). But at first there didn't seem to be any obvious way to use it. So I dug in and found out.
I'm using openSUSE 12.2 with KDE 4.8.5. The search functionality is there, but somewhat hidden.
First, I had to enable and configure the Nepomuk File Indexer. This is done in "Configure Desktop" (also known as "System Settings") -> Workspace Appearance and Behavior -> Desktop Search. First, in "Basic Settings" I checked the box that says "Enable Nepomuk File INdexer". Then I went to the "Desktop Query" tab amd clicked on "Customize index folders..." There, I went through the filesystem tree and enabled only those "folders" (i.e. directories) that I wanted Nepomuk to index. (This is very important. If I enabled everything, including NFS mounts, for example, Nepomuk might degrade my machine's performance and/or never finish indexing.)
The next step was to figure out how, and where, to enter a query. There was no obvious search box.
The first place I looked was in "Add widgets". There I found a "Search Box" widget which I added to the desktop. However, it was broken. I could type into it, but other than displaying the characters I typed it did nothing.
So I poked around on-line and found out that I'm expected to use Dolphin to run searches. This, I found, works quite well once you know how to do it. HINT: CTRL-F.
Another way is to use krunner, which is the box that appears at the top of the screen when you hit ALT-F2. On my system it was configured by default to search the Nepomuk file index.
The advantage of using Dolphin is that you can specify whether you want to search over file names or file contents.