Fala Felipe, beleza?
Então, se você inserir o comando desta forma: $ locate teste, ele vai retornar sim os arquivos em todos os diretórios.
Isso não vai acontecer se você inserir um asterisco no final, como por exemplo locate teste*.
Em suma, funciona assim:
# aqui o locate busca todos os arquivos que contenham "teste" no nome.
$ locate teste
# aqui o locate busca arquivos que comecem com a palavra teste no direitório atual.
# aqui cabe uma observação, como você não separou o argumento com aspas, o bash interpreta primeiro o "*".
$ locate teste*
# aqui ele vai buscar arquivos que comecem com teste no sistema inteiro.
# note que seu arquivo não começa com "teste" e sim com algo parecido com isso "/home/Felipe/teste",
# logo, seu arquivo não será encontrado.
$locate "teste*"
# aqui o locate vai procurar todos os arquivos que tenham teste no meio, semelhante ao seu exemplo.
$locate "*teste*"
Se você notar, no último exemplo, mencionei que 'locate teste' é semelhante ao 'locate "teste"', então por que executar o segundo exemplo?
Ele existe caso você queira especificar a sua busca, assim como fazemos no comando ls.
Um abraço!