What does Ubuntu have? Well, for starters, we have Beagle. Beagle has been around for a while now, and works pretty well. We've also, as of Feisty, got Tracker. Tracker aims to be fast and efficient, and also includes support for some fancy metadata storage features (if I remember correctly).
So which search tool should you choose, Tracker or Beagle? Well, Tracker seems to be faster and lighter on memory, but Beagle is a more mature project and is able to index more (such as emails, which Tracker doesn't yet have full support for). I'd personally choose Beagle at the moment, but Tracker looks promising and might well prove to be a superior alternative in the future.