If nautilus-search-tool is installed, then it should appear when you right-click in the directory (the white space) in nautilus and it should report results from subdirectories too (options for symlinks, hidden files etc can be defined too). If you just installed it, consider doing a logoff/login.
When you press a Ctrl-F or press the button you mentioned, then the search bar appears and you can filter (aka search) the contents of ther current directory.
Hope these help. There are many ways to search for files, gnome-search-tool, beagle, updatedb/locate (cli), find (cli), to mention some of them and at least all of these work well.