How to install the locate command?
sudo apt-get install mlocate should install the 'locate' command.
mlocate maintains a database of all your files and is re-indexed once a day by default. If you want it to re-index immediately then run sudo updatedb from the command line.
If you get a cannot stat error when you run locate, then you need to run sudo updatedb to populate the database, just as if you wanted to re-index immediately.