Something this bad starts at the workstation you use to maintain your website. Make sure it is not infected with password stealers and that it has not been compromised.
Only after that, move on to the webserver. Change your web server access passwords, notify your hosting provider and have them burn the server to the ground. They need to know this happened so they can make sure the server hasn't been rooted or otherwise compromised.
After that, this web server recovery is a total wipe and reinstall from scratch.
I'd take known good database and application backups, restore them on a test server off the net, apply all security patches that weren't properly kept up and then change all admin passwords on the Magento install.
Only then would I back the test server up and upload the site contents to the live server.
As to experiencing it, it may or may not be a Magento security breach. Depends on what Magento security patches you failed to keep up with. A simple security breach from a compromised workstation or server account password would do it.
