Yeah, I was into machinima for a while, a guy involved in machinima even gave a talk at TCD.
Anyway, there are generally two ways to do it, either you script the entire sequence and record from scripted cameras, or you set things up in multiplayer and have all the characters and camera controlled by other players in real time, like actors.
You can mix and match them naturally.
Given the potential for modding that a lot of games have, the possibilites of machinima are gigantic. They range from something (relatively)simple like making scenes in a game universe(Red vs. Blue), or the machinima eqivalent of a total conversion mod where you create an entirely new scenes with new animations, models, levels etc. based on whatever you want with only the mechanics of the game engine left (Hardly Working).
In the end, it depends on what effect and scene you want to create. Then look at various games and game engines and see which ones will give you the structure you need while also being flexible and customisable for what you want to do.
Decent Wikipedia article: http://en.wikipedia.org/wiki/Machinima