gcc … -llua procura um arquivo chamado liblua.so se você estiver vinculando dinamicamente (o padrão) ou liblua.a se estiver vinculando estaticamente.
Você pode procurar o (s) pacote (s) contendo um arquivo com um certo nome com apt-file . Você também pode fazer essa pesquisa online em packages.ubuntu.com (“Pesquisar o conteúdo do pacote”, certifique-se de selecionar distribuição e arquitetura). Mas…
$ apt-file search liblua.so
$
O que está acontecendo é que o Ubuntu envia múltiplas versões das bibliotecas Lua, e elas não são compatíveis com binários, ou seja, você precisa selecionar o que você quer em tempo de compilação.
$ apt-file --regexp search '/liblua.*\.so$'
<lots of hits>
A partir do natty, a versão preferida de Lua é 5.1 , com 5.0 e 4.0 também disponível. As bibliotecas lua correspondentes para vinculação são liblua5.1.so , liblua50.so e liblua40.so (você pode listar os arquivos em um pacote com dpkg -L liblua5.1-0-dev ou apt-file list liblua5.1-0-dev ). Portanto, você precisa alterar seu comando de vinculação para -llua5.1 (ou -llua50 ou -llua40 se você precisar de um binário compatível com sistemas mais antigos).