I have recently had to do this for a client whose store was compromised.
TLDR;
Assume all code on your site is compromised. Download new software/code from known good sources only. Install latest security patches. Use secure server/file settings. If you must re-use code from your site, it must be thoroughly audited by an experienced developer. Change all logins/passwords.
Longer;
We decided to spool up a brand new server (new OS) and install a fresh copy of Magento, patched up to the latest version.(In our case we installed 1.9.2.4 instead of the 1.7 the site was previously running.)
Then we re-installed all the themes and plugins using only files re-downloaded from the plugin developers.
The customizations that had been made to the modules and themes were only installed after the code had been thoroughly audited by a developer.
All passwords were changed and file permissions on the server were set according to the Magento guidelines: http://devdocs.magento.com/guides/m1x/install/installer-privileges_after.html
All logins were changed and secure passwords used.
Hope this helps