The short answer is: class-loader magic.
StubOut uses ASM to modify classes, to make them amenable to stubbing. We add a little check to the front of every method to see whether that method has been replaced, and to substitute a call to its replacement if it has. And when we're asked to load a class A that has been replaced by class B, we read class B instead and rename it to A as we're loading it.
The tricky part of all this is that the test classes are executed in the original class loader first, and only when a particular test method is run do we fire up our class loader, reload the test class, and then run the test method on the reloaded test class instead of the original one.
A good rule of thumb in Java is: play with class loaders and you're playing with fire. Even though StubOut's class loader is very simple and straightforward -- as class loaders go -- it can still leave you with bizarre exceptions from the darnedest places. (See the FAQ for an example of this.)
StubOut's class loader delegates as little as possible to its parent class loader. This maximizes the number of stubbable classes. But sometimes you'll run into a class that behaves oddly when it's been loaded this way. Your way out of this kind of situation is to exclude the problematic class from StubOut's loader, so that it gets loaded by the parent loader instead.
If you're running with a Sun JVM, and you encounter strange errors, try excluding the "sun" package.