1. Non-solid blocks
In Lumines, when you land a 2x2 block on top of previous ones so that half of it is left hanging in the air, it doesn't remain that way. Instead, the blocks that were left on top of nothing break off and fall down until they hit something solid. It doesn't sound very revolutionary, and indeed it's not particularly new. In Lumines this mechanic ensures that it's more challenging to figure out how a block will end up. Players need some experience to see what's the best way to drop a block into a particular spot on their "construct".
It also means that when a player "undermines" (connects and destroys blocks so that some of the destroyed blocks are underneath other blocks), they again need some experience to see where all those blocks that fall down will end up. In short, the mechanic makes the game less static, and therefore more challenging to entirely figure out. Setting up combos that make use of this mechanic is an art form in itself, and something I have yet to master.
2. The beat line
In Lumines, when the player connects rectangles of four or more blocks, these are not immediately removed. Instead, they are marked for removal. A beat line constantly passes over the playing field, left to right, and as it moves, it erases all blocks marked for removal (and scores them). This mechanic affords big combos, as the player can build lots of rectangles for removal before removal takes place. It also adds a bit to the player's cognitive load as they need to be aware of which blocks are not going to be around much longer while they are placing new blocks. Combine with the previous mechanic, this makes it sometimes quite challenging to figure out what's a an optimal move for a situation.
Another interesting dimension about the beat line is that its speed affects how a level plays. Levels where it moves slowly afford big combos, but are harder because more blocks will accumulate on the screen between removals. This is especially true in levels where the beat line is really slow, and the falling speed of blocks is really fast. The difficulty of levels in Lumines is therefore controlled by two parameters instead of one, which adds a lot of variance to progressing through the game. Which brings us to the next point:
3. Nonlinear difficulty progression
Lumines does not simply change both its difficulty parameters constantly towards more and more challenge, but instead some levels downplay the challenge in one of the parameters and increase in the other. The levels are arranged such that the toughest levels are often followed by somewhat easier ones. I like how this gives the player a second chance after a hectic level which is almost guaranteed to mess up their stacks. Often in these slack levels scoring is not as important as improving the block structure for the next tougher level.
The downside is that this makes the game much longer to play, as it becomes "impossible" way slower than games where only one difficulty parameter constantly ramps up. After the full cycle of 20 levels, the overall falling speed of blocks increases, so eventually the situation is going to get out of hand (for me its at the first half of the third cycle). The definite upside is that one mistake is not going to ruin the entire game. There is always hope. "If I can make through this level, I can fix that problem. Not all is lost."
Lumines (Supernova) does a lot of things right. It puts a huge cognitive load on the player and succeeds in keeping a player in flow for a long time by introducing non-linear difficulty progression. Thanks to the huge cognitive load, the game is really hard to master. It stays interesting a long time.