It is probably due to a naming convention confusion that occurred when they first added that addon and maybe nobody has bothered to fix it... I'm not sure. In general, there's no magic here. You can locate the Allegro libraries (shared objects) in your file system, named exactly as they are on your command line, except for having a lib prefix and so suffix per standard, as well as various symlinks with various degrees of version number (usually).
locate liballegro | grep /lib
Rather than manually specifying linker flags, you should probably be using pkg-config to manage your linker flags for you.
gcc -o test -Wall $(pkg-config --cflags allegro_5 allegro-dialog_5) \
test.c $(pkg-config --libs allegro_5 allegro-dialog_5)
It's kind of surprising that you managed to compile and link without specifying custom header and library directories. Either you modified the install prefix or maybe Ubuntu includes /usr/local by default to make things easier (and potentially less secure)...