Acontece que não é apenas com a allegro que vc precisa linkar. Existem outras bibliotecas com as quais vc também precisa linkar para compilar programas que utilizam allegro.
Para facilitar a sua vida, quando vc instalou a biblioteca allegro também foi instalado o programa allegro-config que é de grande ajuda.
Rodando em um terminal
allegro-config --libs
vai retornar uma linha com opções para linkagem que devem ser passadas para o gcc. Aqui na minha máquina ele retornou
-L/usr/lib -lalleg-4.2.0 -lm -lpthread -lXxf86vm -lXcursor -lXpm -lXext -lX11 -ldl
Mas pode ser que na sua máquina seja diferente. Perceba que ele vai linkar com várias bibliotecas além da allegro (o erro de referência indefinida para o comando "pow", por exemplo, corresponde a não ter achado a biblioteca matemática "m", que requer que vc passe a opção para o gcc "-lm").
A maneira mais prática é vc compilar seu programa é usando o comando
gcc nome.c -o nome `allegro-config --libs`
Assim a saída do comando "allegro-config --libs" será passada diretamente para o gcc e o programa deverá compilar numa boa.
Off-topic: ah um bom tempo atrais eu estava mexendo com allegro e na época eu estava lendo o livro "Game Programming All in One (Second Edition). Ele é muito bom e o autor utiliza a biblioteca allegro e fala bastante sobre ela. Ao longo do livro ele vai desenvolvendo um jogo chamado tank wars que é bem interessante e didático. A leitura vale a pena.