How does Java's Dynamic Proxy actually work?

At least for Sun's implementation, if you look at the source code of java.lang.reflect.Proxy you'll see that yes, it generates the byte code on-the-fly (using the class sun.misc.ProxyGenerator).

I suggest that you read Dynamic Proxy Classes:

The Proxy.getProxyClass method returns the java.lang.Class object for a proxy class given a class loader and an array of interfaces. The proxy class will be defined in the specified class loader and will implement all of the supplied interfaces. If a proxy class for the same permutation of interfaces has already been defined in the class loader, then the existing proxy class will be returned; otherwise, a proxy class for those interfaces will be generated dynamically and defined in the class loader. [emphasis mine]

The proxy class is generated on-the fly(hence dynamic proxy) and loaded by the classloader. That's why if you debug applications that relies on JDK proxying you'll see bunch of classes named 'com.sun.proxy.$Proxy0'.

To test my theory you can use an example from Dynamic proxy classes along with the VM parameter -verbose:class which will tell you the loaded classes by the classloader and you shall notice among the classes loaded the com.sun.proxy.$Proxy0.