It's in interesting article, but I think it is possible to give an explanation that should be a bit more clear for people who are not into computation complexity.

The question that is studied, is whether it is possible to finish a given level for one of these games. For the levels in the original games this question is not very interesting, because the games would not be very fun to play if you weren't able to finish them. But given any level, the question whether it is possible to finish such a level can be a very complicated.

Now the problem of finding the solution to such a question is NP-complete if you are able to show two things: 1) that it is NP-hard and 2) that it is in NP.

A problem is in NP if somebody who claims that the answer to a problem is "yes" can backup his claim with a proof that can be checked efficiently. In the case of Super Mario, it is quite easy that it is in NP: somebody who claims that a level can be finished, can just play the level until the end, while you sit next to him on the couch making sure he doesn't cheat.

A problem is NP-hard if you can show that your problem is at least as difficult as a problem that is known to be NP-hard. This is quite a challenge to show and it is what makes the mathematical proof so long. They basically take a well known puzzle from mathematics and show that the "pieces" of this puzzle can be translated to pieces of a level, in such a way that the complete level can only be finished if and only if there was a solution to the original puzzle. This shows that the problem is NP-hard, which wraps up the proof that deciding whether you can finish any level in one of these games is NP-complete.