This problem appears usually if you have a new server and there are no packages installed yet. If you need to use locate command for any reasons, you should run updatedb periodically in order to ensure you have the most recent cache of your file positions.
if you receive command not found error, it usually means you have no mlocate package installed. On most modern linuxes you can install it using your package manager (yum, apt-get, etc). You are also welcome to compile it from source, that can be found at https://fedorahosted.org/mlocate/ . I don’t think you should have problems with this package; you will then be able to run updatedb and locate.
If CentOS yum command will be
yum install mlocate
It is not recommended to run updatedb if you have lots of files on your machine. In this case updatedb execution can slow down your server. But if the number of files is not so high, locate is probably the fastest way to find the files you need.