They use the same virtual machine multiple times between users. You can basically find traces of previous users on their VMs. Now what if somebody installed a keylogger and you're the next one using the VM?
I'm one of the developers in charge of the Sauce Labs' backend and thought I should chime in and confirm with you that that's not the case with our cloud.
Our infrastructure is hosted in our own data center and we've gone to great lengths to never, ever reuse VMs. You can read more about our "security through purity" approach: http://sauceio.com/index.php/2011/09/security-through-purity...