There's a few questions in there, so I'll address them one by one.
What does A x B : C Mean?
Read this as A instances of a B number of inputs to C number of outputs. What you are looking for, if I understand correctly, is a 16x2:1 or a 32x2:1 chip. If C is more than 1, then your chip is significantly more complicated - you would no longer be selecting one input and connecting it to the output. Which leads well into the next sub-question -
Why are there $200+ chips for this simple function?
The specific part you linked is a 1x32:16 wide-bandwidth, DC coupled, buffered, video MUX, which can select any of it's 32 video inputs and output them simultaneously on it's 16 buffered outputs, with a gain of 1-2x. You could sorta think of it as a 16x32:1 with a lot of features. It's got quite a bit more inside than just CMOS switches. It isn't really designed for your function, which is...
How do I connect two memories to a master CPU
The most common method for hooking up multiple memory chips to a driver/controller/cpu is to use a tri-state bus. The address lines drive both chips, and the data bus is shared between all chips. Both chips should have a pin like "output enable", which can be controlled by the CPU. I found this article discussing memory buses at a rudimentary level - it has descriptive images. See Figure 8 for the gist of what I think you want. It is the simplest way of hooking things up, and the way I would recommend if the chips support it.
How would I make one?
Well, I think you were on the right track. CPU buses can be bi-directional, so intercepting the right output enable signal may be risky. The part you were probably looking for was a digital switch, something like this 16x2:1 FET mux. This is the cheapest one at $1.75 each. Wide bidirectional buses are best handled by ICs.
Note
I would check with the maker of your CPU to look for app notes and reference designs regarding memory buses. That will be the easiest way to see if you're on track.
Indeed, you need to at the very least replace the circuit breaker to some sort of signal instead, as otherwise you wont be able to power the lamp. If you were to send the signal as a brief lack of power, you need some to make some bi-stable circuit in the lamp to do the switching.
I would recommend using a micro-controller and bi-stable relay. I would power the µC from a diode bridge and a capacitor, and use the EEPROM to remember the state of the device, and use the brownout/power reset to trigger a switch, i.e. to actuate the relay.
Now any simple push-button in a series chain (i.e. both your wall button and cable button) will trigger a toggle.
I hope you have space for a relay in your lamp-side circuit, as switching mains AC in any other way will be much more complicated...
Best Answer
It would be really helpful if you knew how the switch was wired within the KVM relative to the rest of the circuit to understand the best application of a transistor or IC.
For instance, if the switch is just bringing an input to ground through a resistor, you may be able to sink the current directly through an I/O line
In the absence of specific information on what the switch is doing, you can't go wrong with replacing a switch with a relay. The relay contacts would replace the switch, and you would drive the coil from the Arduino through a transistor (since the I/O line can't drive the relay directly). Of course, you would have to deal with the clicking and the relatively shorter operational life of a relay over a transistor.