Existem várias maneiras de fazer isso. O mais fácil é verificar se gdb está no seu $PATH :
which -a gdb
No entanto, o programa pode ser instalado e não estar no $PATH do seu usuário. Para procurar rapidamente por um executável chamado gdb faça isso:
locate -eb '\gdb'
De man locate :
NAME
locate - find files by name
-b, --basename
Match only the base name against the specified
patterns. This is the opposite of --whole‐
name.
-e, --existing
Print only entries that refer to files exist‐
ing at the time locate is run.
EXAMPLES
To search for a file named exactly NAME (not *NAME*),
use
locate -b '\NAME'
Because \ is a globbing character, this disables the
implicit replacement of NAME by *NAME*.