My Ubuntu version is 12.04.

I'm simply trying to include GL/glu.h in my program, but I get the error:
fatal error: GL/glu.h: No such file or directory

I include it like this:
#include <GL/glu.h>

I have libgl1-mesa-glx-dbg, libgl1-mesa-dev, mesa-common-dev all installed.

Sounds like you're missing the glu package (libglu1-mesa-dev). A quick 'sudo apt-get libglu1-mesa-dev' should solve that problem for you! :)