Currently nautilus only searches the current dir., recursive was added back right after the 3.6.1 release. It could be added back in raring, maybe it will come in 3.6.?, maybe not. (works quite well when enabled https://bugs.launchpad.net/ubuntu/+source/nautilus/+bug/1077415
recursive search in nautilus
Archived thread 2082802 from Ubuntu Development Version. Markdown source: Ubuntu_Development_Version/thread_2082802_recursive_search_in_nautilus.md
Yeah afiak this is only fixed in nautilus 3.7, I really hope they backport this for 3.6 in raring...
I'm using 3.6.2 in quantal with the gnome 3 ppa and its a problem there.