Vinícius,
Esse é um erro de ligação na geração do executável.
Quando você executou o gcc, você passou na linha de comando o parâmetro -lallegro (indicando que o seu programa usa a biblioteca do Allegro)? Você tem que fazer algo assim:
gcc -lallegro -oteste main.c
Se você fez isso e não funcionou, tente trocar a ordem do parâmetro -lallegro no comando, colocando-o no final:
gcc -oteste main.c -lallegro
Como é possível ver no manual do gcc, a ordem em que a opção -l aparece no comando afeta o seu resultado: http://gcc.gnu.org/onlinedocs/gcc/Link-Options.html .
Se isso não resolver o problema, então talvez você tenha tido algum problema na instalação. Consulte o diretório /usr/lib da sua máquina e verifique se há nele arquivos cujo nome começa com "liballegro". Se não houver, é porque a instalação não foi concluída com sucesso.
Kelly