Generally you should use the gp2x-allegro-config script in your compile and link command lines. It fills out include and library paths, and links the right libraries for you. The main options are:
If it's one command which is both compiling and linking, pass both flags.
As a side effect of the configure line above, gp2x-allegro-config will also force your binaries to link staticly. If you don't like it, edit the script and take out the -static option.
The examples will have been built automatically, but as an example of building your own program, try copying the exjoy.c file from the examples directory to somewhere fresh. Then you can compile it:
gcc -o exjoy.o -c exjoy.c -O2 -Wall -Werror -g `gp2x-allegro-config --cflags debug`
And link it:
gcc -o exjoy exjoy.o `gp2x-allegro-config --libs`
Then write a .gpe wrapper script that runs './exjoy' and chains back to the gp2xmenu.
Note that it's OK to pass 'debug' when compiling yet not when linking - your own code's TRACE calls will then output to allegro.log, while the library itself will not. Quite a useful setup.