'locate -u' creates an index, or database, of all the files on your system. You don't generally have to do this though, as it's set up to run once a day on most systems. An exception might be if you've just installed a lot of software, then you might want to run it (as root).
'locate <filename>' uses that index to tell you where the file called <filename> is.
In fact, at least on my system, locate is a symbolic link to another program called 'slocate'. Which means that when you call locate, you're really calling slocate. This program does exactly the same thing except that if a user is not allowed to see a particular file or directory, it will bear this in mind when doing a search.