That was for Java4k 2009. Notch was a regular participant in the competition, winning several years with 4k demakes of other popular games (though in that specific year I won :-)). He was experimenting with hand-writing JVM byte code assembly-style and wrote the core engine of a Minecraft-style game in just over 2000 bytes, then got bored with the project and wrote something else.
Due to the way Java4k works (your entry is measured by compressed jar size), every byte can fit a little more than the previous one, so 2000 bytes is actually less than half the allotted space.
Demakes are an interesting concept. For example, how little could you get away with doing for a demake of the first level of the original Crash Bandicoot? By that I mean, how little time could you get away with spending on code and graphics and still have it be recognizable by someone that had played said game in the past? How little and still have them identify it as a version of Crash rather than just being reminiscient of Crash? How little and still be visually pleasing? How little and still be enjoyable to play?