The way 'locate' works is to use a searchable database of the files on your computer - that's how it works so fast. But you have to keep the database up-to-date. To do that, run 'updatedb' as root. To make this happen automatically, you can put a script in /etc/cron.daily that looks like:
Make sure it's executable (chmod +x /etc/cron.daily/updatedb) and it should be run automatically once a day to keep you up to date.