This answer is based solely on the information here and the original Parallel Universe video.
There is a part of the game's code that detects whether Mario is standing on the floor. This part of the code uses 16 bits to process Mario's position in the X, Y and Z direction (so 48 bits total, but 16 bits per direction). 16 bits is enough to store a number between -32768 and 32767. The Y direction (up and down) is irrelevant, so let's focus on X and Z.
Let's say there is a floor you can stand on, at coordinates X=0, Z=0. If Mario is at the same coordinates X=0, Z=0, then the code will (of course) detect that he's standing on the floor at X=0, Z=0. And Mario will be able to stand on the floor.
Now let's say Mario is at coordinates X=0, Z=32769. When the game runs the code to check whether he's standing on a floor, it will try to store 32769 in 16 bits. 32769 is out of the range that will fit, and it wraps around to -32767. Then, the floor-checking code will look for a floor at the coordinates X=0, Z=-32767, which is not Mario's actual position!
If Mario is at X=0, Z=65536, then it wraps all the way around back to 0. Basically, any multiple of 65536 gets removed. So if there's a floor at X=0, Z=0, then Mario is allowed to stand at X=0, Z=0, or at X=0, Z=65536, or at X=0, Z=131072, or at X=65536, Z=0, or at X=65536, Z=65536, or at X=65536, Z=131072, or so on.
This makes a grid of valid positions for Mario, which is the "PU grid" (Parallel Universe grid). If Mario is in any position where it gets wrapped around for the floor check (i.e. any of his coordinates are less than -32768 or greater than 32767), then we say he's in a parallel universe.
This "bug" specifically affects the floor check. It does not affect many other parts of the game code, so many features of the game do not function in a parallel universe way, including things like wall checks.