Most likely answer would be “image map” but that’s not a WP issue, so you will need to google for it.
Image map looked far away from what I was after…many websites seem to do it with individual links?
You wrote:
Well, I’ve made a version of that header image with a cool horizontal navigation menu on it (basically a cool font overlaid on the image).
For me that means that you modified the image (in an image editor) and the fonts are there on the image. Part of the new image. And in that case image map is the only thing you can do.