The first method of course is to use a graphic display that has 2 video inputs (2 VGA, 2 DVI ,or 1 DVI and 1 VGA).
Take the example of a display that has both VGA and DVI input, and the two computers have graphics cards with different outputs (the first PC with VGA output, the second PC with DVI output).
You can then connect the 2 cables (VGA and DVI) for 2 PCs simultaneously with the same monitor. Then you press the button that changes the "display source" (VGA or DVI) depending on the PC you want to use (see).
Of course this does not solve the problem of having to use double keyboards and double mouse!
In the first case, the test was done for example with a Samsung SyncMaster 2243WM that has one entry VGA and one DVI, and it works!