Yes they will degrade, but if you get a good one and use really good cables, then you probably won't notice it.
Some features to consider:
USB or PS2 or both?
Most are just PS2. USB is becoming available. I have used a Belkin SOHO series KVM that supports both USB and PS2. It was okay except for the fact that it only allowed PS2 keyboard/mouse to be hooked up, then with each computer you decided whether you wanted to connect it with PS2 or USB. It worked okay for my USB-only Macs, but I did notice that the mouse seemed to have a slight stuttering tracking.
USB device sharing/switching?
My new IOGear Miniview III KVM allows me to have usb devices, say a scanner, that any device on the switch can access.
Keyboard hot-key switching?
This doesn't seem like a big deal, but I like it. Switching with a hot-key is just cool.
On-screen display?
This puts a readout overlay on the screen to identify what computer you just switched to. Some KVM let you set it to go away or be always on. Always on is nice when you are running it for a server room setup.
Beep.
Both my Belkin and IOGear beep when I switch computers, the IOGear is quieter though. It would be nice to be able to turn off the beeping.
Cables.
The IOGear came with 4 bonded video/usb cables.