I work in a school, and have seen, used and implemented a few different multi-seat systems in the past few years with the aim of getting banks of workstations into classrooms.
For a Linux machine stuffed full of extra two-port graphics cards, with no propitiatory hardware needed, try Userful. You can download a free two-user demo, which seemed to work well enough when we tried it in a classroom. The software does cost money, though, and is comparable in price to similar Windows-based solutions. Buying matching compatible hardware, USB hubs, keyboards and so on (and configuring X for dual-port output) is a right palaver, so if you have the money to hand then buying their all-in-one hardware and software solution is probably the best idea.
NComputing's system works with their software and propitiatory hardware, a PCI card that you plug in the back of your PC to attach 5 workstation dongles that you then plug keyboards, mice and sound into. Note that these are PS/2 keyboards and mice (something to do with the system making use of PS/2 timing signals, I believe). One PCI card does 5 workstations, you can have up to 10 workstations by using 2 PCI cards, although I would point out that it's getting increasingly difficult to find decent motherboards with more than one PCI slot these days.
We use NComputing's older 3-workstation solution in our school staffroom on a Windows machine, and it chugs along okay. It seems to handle graphics and video better than you might expect, and the YouTube demo on their site shows their system running on one consumer-grade Dell PC with all 10 workstations running video, so a pretty standard PC (quad core might be a good idea) with some extra RAM (8GB is quite cheap these days) should handle most things.
I've actually got to repair the above-mentioned staffroom machine tomorrow, mainly because being a Windows machine the staff have stuffed it full of spyware and goodness-knows-what until it simply fell over. The licensing routine for the software is a bit over-protective, although seemingly this has been rectified in newer versions. It's worth pointing out that having one machine running multiple workstations does create a single point of failure.
From speaking to NComputing at a trade show in January, I know they were developing a Linux port of their software, although I haven't heard anything from them recently. Contact them for more details.
MiniFrame's SoftXpand system sounds similar to both of the above, using multiple standard graphics cards to run Windows workstations. I don't think they have a Linux version, although it's worth a check.
Double and triple check your Windows licensing before you use such a system with a Windows operating system. As far as me and a bunch of other people have been able to figure out, the best licensing option seems to be Windows Server with the appropriate number of Terminal Server CALs. Various resellers might well try to flog you systems that promise to run 10 workstations from one Windows XP PC, and it might be perfectly legal for them to supply such systems (they are, after all, supplying one PC with one copy of Windows), but you'll need to ensure each workstation is properly licensed (this gets really confusing in corporations and schools with Microsoft License agreements).
Technology has moved on in the year or two since we bought the multi-seat system, and for our new staff work area we bought Acer Veriton N260G machines, which clip on the back of an LCD monitor. Atom processor, low-powered, perfectly capable of everything the average user wants to do, just over £320 ($500USD) complete with widescreen monitor, keyboard, mouse and delivery, so I doubt a multi-seat system is going to save any money, and I don't know how the multi-seat power savings would compare against Atom-powered mini workstations like the Acer Veriton and Revo.
