I've got a Virtual Private Server account with full root/ssh access. What do I need to install on my server and how, so that I can remotely debug my scripts via PHPed?

you have to install dbg.so module and add necessary settings in php.ini.
I believe that everything is described on PHPED FAQ page howto-run-debug-session-t585.html
Feel free to ask if you have and further question(s)

It's my understanding that you use VPN to access to your server. If you asked whether DBG can work through it, I'd answer - no, it's not supported. But you can set up secured tunnel using ssh and work though it.

Thanks for the reply! I access my server normally in most situations, I just use SSH to login as root and configure things, so I think it should work. Now I wonder if there's any stability or performance issues once I've added the shared object to apache? I'm assuming the debug module is only called when the proper headers are sent via PHPed, so hopefully it won't cause any performance probs, but I'm still a bit worried about stability. Guess I'll just give it a try and see what happens.

you have to set debugger.JIT_enabled=off in php.ini otherwise dbg permanently monitors everything you run and tries to connect to the client in case of errors/warnings (depending on debugger.JIT_level setting).