The Grima objective-ally card says "If free of encounters, the first player gains control of Grima."

I believe that means he moves around with the first player marker, correct? However, I thought I read there's a distinction between similar wording, where at times such an objective-ally doesn't follows the first player.

If so, what is it? (Or maybe I'm completely wrong on that.)

Grima's "control clause" is passive, so it always checks and he moves around the table as first player passes. There are some other objective allies that the first player gains control of as a response. Since responses are one-time effects, those allies would not move around the table.

Exactly. If there is a one-time effect that give them (probably "when revealed", a "response" or "forced") then the control will not change.

For example: http://hallofbeorn.com/LotR/Details/The-Hidden-Way-HoN

If this is a passive effect it is always checked so when first player change objective move around too. Grima is a good example