I've used the "locate" command for many, many years on various POSIX systems. It's a very fast search for filenames containing the specified string on your machine.
Here's a Mac command that simulates "locate" using the Spotlight database:
mdfind "kMDItemFSName == '*$1*'"
It's not as fast as locate, but it is always up to date (as opposed to locate, which relies on cron to reindex the disk periodically). As anyone can guess from the syntax, it's also very flexible. To find all files that originated as email attachments from my friend Glenn, for example, I can do:
mdfind "kMDItemWhereFroms == '*medianinja.com*'"
Or to find all files bigger than about a gigabyte:
mdfind "kMDItemFSSize > 1000000000"
(the WhereFroms search is fast and the size search is dramatically slower, maybe because all files have sizes but not many have kMDItemWhereFroms metadata)
To get a list of the supported keywords, type "mdimport -A"
Update: I found the Spotlight query syntax to be useful