Understanding Digital Multiplexing
There are three scenarios that I see:


The selector lines would either to run with the data line (as you suggested)
The selection comes from an external entity that feeds into both, the MUX and DMUX
The selection lines are controlled by a synchronised entity e.g. a clock or a counter powered by a clock.