What is the difference between locate/whereis/which

which finds the binary executable of the program (if it is in your PATH). man which explains more clearly:

which returns the pathnames of the files (or links) which would be executed in the current environment, had its arguments been given as commands in a strictly POSIX-conformant shell. It does this by searching the PATH for executable files matching the names of the arguments. It does not follow symbolic links.

whereis finds the binary, the source, and the man page files for a program. For example

$ whereis gimp
/usr/bin/gimp /usr/lib/gimp /etc/gimp /usr/share/gimp /usr/share/man/man1/gimp.1.gz

You can get extra detail by passing the output of these commands as arguments to ls -l or file

$ ls -l $(which gimp)
lrwxrwxrwx 1 root root 8 Jun 30 19:59 /usr/bin/gimp -> gimp-2.8

$ file $(which gimp)
/usr/bin/gimp: symbolic link to gimp-2.8

locate indeed finds all the files that have the pattern specified anywhere in their paths. You can tell it to only find files and directories whose names (rather than full paths) include the pattern with the -b option, which is usually what you want, and gives a less unwieldy list.

locate is fast because it uses a binary database that gets periodically updated (once daily, by cron). You can update it yourself to ensure recently added files are found by running sudo updatedb

One more thing about locate - it doesn't care whether files still exist or not, so to avoid finding recently deleted files, use -e. Often I also pipe to less as the list can be long. Typically I do:

sudo updatedb && locate -b -e gimp | less

How Unity's dash works is explained here - it uses Zeitgeist to index system files and learn from usage patterns, and enables other applications to make use of this data, so it is doing a lot more work than locate.