How it worked was that each lemming was actually treated for collision purposes as if it was a single dot, and that was tested against some kind of bitmap for where there was solid ground.
(I think! I remember, with a friend, implementing our own version of this, and that's definitely how our version worked.)
So this is less realistic than other ways of implementing lemming behaviours, and easier to implement than some kind of more 'correct' collision approach, but gave the gameplay a very nice precise feel.
I always wondered what kind of challenges that imposed on the sprite-based consoles of the day like the NES and especially something like the Gameboy.