Does anyone have a Xen bridge installed to connect a public IP VM to a private IP VM?

If so, how did you do it?

Not sure what you mean are these VMs running on the same machine? Seperate machines? If they are running in the same Vm you could setup two dummy interfaces on the Host and direct traffic fromt he Private IP VM to the dummy interface that acts as the gateway to the public IP VM and set up a route on the public IP VM to dirct traffic for the Private IP VM to the dummy interface acting as gateway to the Private IP VM.

Or you could add additional interfaces to the VMs and set those VMs on the same private IP network, then the two VM could talk directly with each other.