Kolob's answer is entirely correct.
Personal anecdote: I was using Synergy over Wifi and the performance was utterly abysmal. Just random lags, stoppages, clicking on tabs would take seconds to update. Truly terrible. Based on his answer I went and hooked up my machines using hard-wired ethernet and everything became butter.
I post this as an answer because the difference between my setup and the one recommended by Kolob is that I used an actual gateway (I used to use it as my wireless gateway before my ISP provided their own hardware.) With this technique, each machine still gets to connect to the internet via Wifi as normal, but my gateway acts simply as a vehicle for providing a separate subnet. (the "WAN" port is not even plugged in -- but the router is providing DHCP and the subnet) That way, I don't have to worry about disabling any existing network, etc., and both can live together harmoniously.
When configuring Synergy, just make sure you're using the IP addresses of the subnet provided by your gateway rather than your Wifi connection. A simple ipconfig or ifconfig should facilitate determining which IP address you want the client to use (the server will be bound to all its IP addresses, so you don't have to worry about it).
On a Mac, make sure to go to System Preferences > Network and then click the little gear icon on the bottom of the list of network interfaces you have (i.e. Wifi, LAN, etc.) and click "Set Service Order". Then drag to make sure your actual ISP interface (i.e. Wifi) is ordered above your ethernet (LAN) interface. Otherwise you won't get any internet on your Mac. (didn't have this problem on Windows for whatever reason)
