Gewoon met de meegeleverde software Tracker. Ik geloof dat dat sinds Ubuntu 9.04 niet meer meegeleverd wordt. Even je pakketbeheerder openen, tracker aanvinken en installeren. Start vervolgens de instellingen van Tracker met Systeem -> Voorkeuren -> Indexing Preferences (of iets dergelijks, zit niet op gnome). Daarna zul je onder Toepassingen -> Hulpmiddelen een tool vinden om bestanden te zoeken met Tracker.
Tip: voeg Deskbar Applet (actiebalk in het Nederlands) toe aan je paneel. Hiermee kun je zoeken met tracker, zoeken op wikipedia/google, zoeken naar mail, enz enz enz.