I think you might be confused because Nemo and Nautilus would show the same icon and name, but searching for Nemo under the application menu should bring it up:
You can also use generic names like "explorer" or "files".
The reason it appears as the same app is because Nemo is a fork of Nautilus, so they are very similar. Please see this thread to know how you can change this:
Nautilus does search the content as well. Just start typing right in the "address bar" and it should return results even if the files are not in the same folder that Nautilus is on:
