How is this multiplexer built? (on a logic gate plan)
As I mentioned in my comments: Whomever made this video, has the wrong perspective of a multiplexer. The first picture appears to be a decoder.

Multiplexers are used for selecting an input channel to determine what serial data gets through. Serial data is different than parallel data in that it uses a waveform (mostly PWM, pulse width modulation) to send information. It's typically used for I2C or SPI interfaces, though I'm sure there are some other applications that I can't think of.

Decoders are used for basically converting binary to decimal and uses parallel data transmission. As you can see in your first picture, it's usually (what's supposed to be) decoders to call an address to a cell of information. Processing units typically use decoders to call addresses for external memory, like RAM or your storage device. So in that screen shot of that video you provided, it's using the binary value 0001 to select row 1. 0001 is a binary number for, you guessed it, 1. 0010 is two, 0011 is three, etc.

The difference between serial and parallel data transmission is that serial data doesn't send all of its information all out at once. It may be extremely fast at sending information but it doesn't happen instantaneously at the exact same time. Parallel data does, however, send all its information at one time. One downside of parallel data is physical spacing because it requires more "wires", so to speak, (or vias if you want to get into circuit boards) to travel from one place to another.