I don't own any OSX machines, so I can't help you there, but Linux is a fairly simple straightforward matter.

On Ubuntu, it's pretty easy.

sudo apt-get install liballegro4-dev

Then to compile and link with allegro 4, you use allegro-config. Type it at a prompt to see options.

g++ -Wall -Wextra -Wshadow -g -o main.out `allegro-config --cflags` main.cpp `allegro-config --libs`

EDIT
On versions of Linux that don't have packages prepared for allegro (they should all have one for Allegro 4 by now...), you can build from source using cmake.

Homebrew might have binaries for Allegro 4 on OSX.

yes, static link.

On Windows this is no problem, but on Linux, even if you static link, you'll still have a bunch of dependencies on system libraries. Use ldd to list them, and then copy them into your game folder. Then write a launcher script that adds this library directory to your LD_LIBRARY_PATH environment variable.

g++ -Wall -g -o main.out `allegro-config --static --cflags` main.cpp `allegro-config --static --libs`

export LD_LIBRARY_PATH=libdir/:$LD_LIBRARY_PATH

Even if you do static link, you should still distribute a single zip file for each OS you use. There's no point for me to download an OSX binary, for example.

Bump for progress and possible questions.