Synergy?
Synergy is a program that runs on Windows/Linux/Mac and allows for the sharing of a keyboard and mouse between multiple machines. Synergy is a client/server architecture -where there is one server and multiple clients connect to it. Synergy configures the sharing by specifying which screen is to left/right/above/below others.

Setup
This tutorial assumes that you want the Linux box to be the synergy server and the Windows box will connect to this server.
This tutorial also assumes that your Linux screen is to the left of your Windows screen - but that is easily changeable. This tutorial assumes you are running Fedora or Ubuntu. Most of the information in this tutorial comes from http://www.mattcutts.com/blog/how-to-configure-synergy-in-six-steps/ and other tutorials.

Server Side (Linux Box) Instructions
Install Synergy

Open a Terminal and, if running Fedora, run the command:

sudo yum install synergy

Or in Ubuntu:

sudo apt-get install synergy

This will download and install the latest version of synergy we have access to.

Configure Server Settings

As root, create a configuration file in the /etc directory called "synergy.conf":

sudo gedit /etc/synergy.conf

In it add configuration that looks something like this:

section: screens
linuxbox:
windowspc:
end
section: aliases
windowspc:
<YOUR PC NAME>
linuxbox:
<YOUR LINUX NAME>.local
end
section: links
linuxbox:
left = windowspc
windowspc:
right = linuxbox
end
section: options
screenSaverSync = false
# My KVM uses Scroll Lock to switch screens, so set the
# hotkey to lock the cursor to the screen to something else
keystroke(f12) = lockCursorToScreen(toggle)
end

In the above configuration, replace:

<YOUR PC NAME> - with your PC's machine name.

This can be found by going to the Control Panel, and then opening System. Then clicking the Computer Name tab.
It should be something like - BOBSWINDERPSPC.

<YOUR LINUX NAME> - with your Linux machine's name.

This can be found by running the following command in the Terminal:

uname -a

It'll be something like my-linux-box.

Client Side (Windows Box) Instructions
Install and Configure Windows Client.
On the Windows machine, go and download Synergy from here:
http://synergy-plus.googlecode.com/files/synergy-plus-1.3.4-Windows-x86-r1.exe (direct link).

After installing this application, open the application and set the program to:

Use another computer's shared keyboard and mouse (client)

Then for the Other Computer's host name, use the name of the Linux box you discovered earlier. Something like:
my-linux-box.local

Connecting
Test out your configuration
On your Linux machine, from the Terminal, run:

synergys -f --config /etc/synergy.conf

This will start the Synergy server in test mode with your configuration file.

Now on the Windows machine, click the "Test" button to start the Windows client.

You should now be able to move your mouse back and forth between machines.
(Try copy and pasting as well! RAD!)

Setting and Forgetting
We want these programs to run automatically on startup.

Windows Client

For the Windows client, you can click the "AutoStart" button and start it up when your computer starts up. If it won't let you save this configuration, make sure you are running Synergy with administrator rights.

Linux Server

Here we want to create a new startup process that has the synergy server starting with the configuration file we wrote.

Click the System drop-down menu and then navigate to Preferences -> Personal -> Sessions

Click the Add Button

For name: Synergy server
For command:

/usr/bin/synergys --config /etc/synergy.conf

You can leave comment blank

Security
By default, synergy is unsecured. This means someone could sniff the traffic it sends over the network.

Some information on encrypting this traffic using ssh can be found:
http://www.cs.uu.nl/technical/services/ssh/putty/puttyfw.html

Another tutorial for setting up ssh based encryption for synergy can be found here:
http://tech.jonathangardner.net/wiki/Synergy_%2B_Putty_on_Windows