<p>As a programmer I have no idea how one would go about programming menus for a DVD, I have heard that this is possible, and even seen basic games using DVD menus - although it may very well be a closed-system. Is it even possible and if so, what language, compilers etc exist for this?</p>

There are a couple of open source projects that can create DVDs plus menus. I recently used
dvd-slideshow
to create a simple dvd with menus etc. Another one is
DVD Styler
. All of these programs are basically a front-end for various command-line tools for encoding, menu creation etc. Since these are open source projects you can have a look at the source and check out how they accomplish this.