So, I bought a simple USB switch, plugged the Mac keyboard into the input and the Mac and laptop into the outputs. I press 2 buttons (one on the monitor and one on the USB switch), I can switch between Mac and PC very quickly!
That left me with my next problem, and the reason for this post. While the Mac keyboard can map to all main Windows keys, I was not happy with the default mapping. Take a look at standard Mac and PC keyboards:
The Mac keyboard puts the Alt key right next to the Control key, but a Windows keyboard puts the Windows key (opens the Start menu) between Control and Alt. I'm not really a touch-typist, but this throws me off something fierce. So, I start looking at ways to re-map keys in Windows, and the easiest way I found was KeyTweak. Here's a screenshot (click to see the full-size image):
I won't try to explain all of KeyTweak's features here, but it's pretty easy to re-map "normal" keys like Alt and Windows just using the GUI. If you have both keyboards available (as I did by using the laptop's keyboard), you can also use a "teach" mode to re-map some of the harder keys, like Volume Up/Down, Mute, and PrintScreen (one of my favorite keys - use Alt-PrintScreen to take a screenshot of the active window and store it in Windows' clipboard).
My exact setup is shown in this "raw map" view:
Feel free to download my Mac keyboard mapping for KeyTweak to use as-is or as a starting point for your own custom mapping.
P.S. If you're looking for the opposite functionality, MacWorld has a nice article on using a Windows keyboard with a Mac or you can try DoubleCommand.