I've added a map (OpenLayers) in one of the CMS templates to let the page editors put markers in geographic locations.

However, I've got a problem: As I switch between subpages in the CMS, the map won't load. It requires a full page reload (F5 in browser) to make the map show up. Which, I guess, is to be expected, as subpage navigation is executed dynamically in AJAX, right?

So my question is: where do I hook up my JS map initialization function so that it is called each time a CMS subpage containing a map is loaded?

I'd need to see a working example (i.e. some code) to see what is going wrong, I can say that when I did this with google maps api I never had any issues - except learning the API - maps displayed as required with no issues.

Actually, let's forget about maps for a second. Let's talk about putting any JS code in a subpage template. (And when I say "subpage", I mean CMS subpage for editing pieces of content, of course, and not the public-facing website.) Like literally alert("ok"). Does it pop up each time you switch between subpages? Because it doesn't seem to be doing that for me.

By Sub page you mean it appears in a the second level navigation? I wouldn't have expected the unexpected there - as much as if it is in an included template...

Regarding putting JavaScript in the template - that is normally frowned upon, instead I'd use...

within the template...

<% require javascript(cms/javascript/LeftAndMain.js) %>

within the page init...

Requirements::javascript("cms/javascript/LeftAndMain.js");

for more info...
http://doc.silverstripe.org/javascript