For this kind of scripting, the host game exposes functions that can alter the game's state. Scripts by level authors may call these functions, often depending on conditions the authors make up. Lua and Python are commonly used for this. You could roll your own replay-like language if embedding full-fledged programming languages seems like overkill.
Arbitrary scriptable events can introduce solution twists you're forced to explore first. This is welcome in action games, where your knowledge of what's happening is limited anyway.
But I feel that such tailoring clashes with contemporary Lemmings level design: You should be able to solve most of a level by pausing near the start, then look and think. Hidden traps and scripting would seriously screw with that idea.
Clones had scripted events. Terrain would move if your Clones reached certain areas.
-- Simon