Você está procurando por libgdbm-dev :
# apt-get install libgdbm-dev
Em geral, você pode procurar por um pacote como este:
$ apt-cache search gdbm-dev
Ou se você conhece um nome de arquivo que deve ser incluído no pacote, você pode procurar por ele:
$ apt-file update
$ apt-file search filename
Outras vezes, se você conhece um pacote que deve de alguma forma depender do pacote pesquisado - então você pode seguir essas dependências, por exemplo, também via e. apt-cache ou link .