locate uses an index you need to update using updatedb before it is able to find anything.

updatedb may run periodically because of a cron job, but the index is probably missing right after installing it manually.

run these two commands:

sudo apt install mlocate

sudo updatedb

Several distributions made an effort to replace locate with alternative and updated versions of it. For usage the command name is still locate, but the package name should be different, in example mlocate or plocate and there are other alternatives too. The main difference between the old and new versions is they are faster.

You can search the package database to determine which package(s) provide a file with dpkg --search $file

IIRC u need mlocate or plocate...

Is the package named findutils?

Just tried this on a recent Trixie amd64 install. locate isn't installed by default, but there is a locate/stable 4.10.0-3 package and it installs just fine for me.

sudo apt update
sudo apt install locate

Btw, there's also
IFS=:; find $PATH -executable -iname "$1" -print
Speed advantages of a indexed DB don't matter much anymore with nowadays hardware.

I'm pretty sure it wasn't installed by default in the previous version either, and maybe even the one before that. It's a useful utility, after you locate it.