"find" and "locate" are 2 great command line file search tools but not everybody is a fan of the command line. Fortunately there is a GUI for these as well as other Linux search tools: Catfish, a front-end for both "find" and "locate" as well as some other search tools such as beagle, tracker and strigi.
Using catfish is very simple: select the search method (locate, find, tracker and so on), enter the word to search and click "Find". It also has a few advanced options like selecting the file type (text, image, music or video), fulltext search and it can also search for hidden files (as well as a few other options).
To install Catfish in Ubuntu, open a terminal and paste this:
sudo apt-get install catfish
Once installed you'll find Catfish under Applications > Accessories > Catfish.
Install more Catfish backends: Beagle, Tracker, Strigi
By default, Catfish uses "locate" and "find" to search for files, but you can install some additional backends:
Unfortunately Beagle was removed from both Debian and Ubuntu 10.10 (and it seems it's no longer maintained) but you can install it in older Ubuntu versions using the following command:
sudo apt-get install beagle
sudo apt-get install tracker
Once installed, you can customize what tracker indexes by pressing ALT + F2 and entering: "tracker-preferences" (without the quotes).
sudo apt-get install strigi-daemon
Note that for all these tools to start indexing your files you need to log out and log back in.