Ubuntu 17.10 and later
As the type-ahead search was a Ubuntu-specific patch, it got dropped together with Unity in 17.10. However there is a package called
nautilus-typeahead in the Arch repository. Someone took it, compiled for Ubuntu and made a PPA. You can install it by these three commands:
sudo add-apt-repository ppa:lubomir-brindza/nautilus-typeahead
sudo apt dist-upgrade
There is an issue on Launchpad about bringing this behavior back to official Ubuntu.
Ubuntu 14.04 to 17.04
Since the Ubuntu 14.04 LTS release type-ahead-find was the default behaviour in Nautilus again.
You can use a dconf key to switch between the different search modes:
gsettings set org.gnome.nautilus.preferences enable-interactive-search true
disable type-ahead-find in favor of recursive search:
gsettings set org.gnome.nautilus.preferences enable-interactive-search false
Ubuntu 13.04 and 13.10
Nautilus 3.6.X cuts many features from the 3.4 and older versions. Canonical decided to keep using nautilus 3.4.2 in Ubuntu 12.10 because if this even though Nautilus 3.6 was already released. I don't think it is possible to get the old search behaviour in 3.6 but what I did was to install the SolusOS patched Nautilus (also works for Ubuntu 13.04) which includes all the features from 3.4.2 (it really is Nautilus 3.4.2) while maintaining the Nautilus 3.6 skin. I've tested this particular package and it works fine in Ubuntu 12.10 and 13.04.
Alternatively you could install the Nemo File Explorer which is a fork of Nautilus 3.4 that was made due to the Cinnamon dev team being disappointed with Nautilus 3.6, you can get the install instructions here.
Making it your default file browser is a bit more tricky, this blog post worked for me in Ubuntu 12.10 but some users reported the method not to work properly.
There are alternative methods however. See the following question: