Hacked site recovery

Initial steps

Contact your hosting provider, if you have one.
Immediately put the site into Maintenance mode or better completely off-line until you know you've fixed everything. You need to cut-off the connection the attacker has to your server.
- You can make a firewall rule to block connections to the server from all ip addresses and then allow only your ip address. Be careful when doing this since your ip address might change from time to time and you can lock yourself out. If that's the case, allow the range that your IP address is in instead.
- If your site is self-hosted or you have physical access to the server, an easier way is to get a small router and plug the server into that. Do not connect it to the rest of the network or the internet. You are now free to access it directly or via another computer on the same router.
Find all available older databases and file backups
Backup php files, database and data files (Do not overwrite older backups.)
Make a list of all PHP software and programs/packages installed on the same server.
Note main Moodle version and the date of last update and make a list of all contrib modules and custom modifications
Check the legal ramifications of possibly exposing users' private data. You are probably required by law to notify your users and at least tell them to change passwords on any accounts with any service that shared the same password with their Moodle account.
Finally, if you are unfamiliar with the command line or with computers/servers in general, it's best to get someone who is familiar to help you. You are responsible for your users' information that you store, so you want to make sure the recovery is done right.

Remember, everything on the system should be considered untrusted until you know to what extent the hacker was able to intrude (Does he have root server permissions or just access to modify certain files?) Do some forensic research into how the person (or program) got in and what they did before just restoring a backup or running anti-virus software. For all you know, the backup could have been modified to contain a backdoor program that allows the attacker back in later. You want to close the vulnerability the attacker used so it doesn't happen again.

Damage assessment

Find out when exactly was the site hacked.
- Check the modification dates on files. You're looking for any application files that were modified around the time of the initial intrusion. These files are suspect.
- Check your server logs for any suspicious activity around that date or few hours before, such as strange page parameters, failed login attempts, command history (especially as root), unknown user accounts, etc.
- Be sure to take into account updates you've downloaded, as that will change the times for modified system files and/or Moodle.
Look for any modified or uploaded files on your web server - look for oldest file that does not belong in Moodle.

Recovery

Restore last backup right before the incident.
Download the latest stable version and upgrade your site.
Change your passwords.
Depending on the extent of the attack, a complete format and reinstall of the operating system might be in order.
Be sure to implement any fixes you found during your investigation and double-check existing security on the server to see if it can't be improved.
- This also means you should review any customizations/add-ons you made for Moodle. Are you sure you properly escaped all user inputs? What about the permissions on your web server directories and database?

Dealing with spam

Spam in profiles or forum posts does not mean your site was actually hacked.
Use the Spam cleaner tool (Settings > Site administration > Reports > Spam cleaner) regularly to find spam.

Prevention

Always keep your site up-to-date and use the latest stable version. Git is an easy way to do this.
Regularly run the Security overview report (Settings > Site administration > Reports > Security overview).
Understand how to properly set permissions and file ownership to maximise security. If this is a mystery, you mustn't ignore it - read about it or ask in the forums!
Make sure you have a properly configured firewall/packet filter on your server.
When making customizations to Moodle or other web applications on your server, be sure to review your code and make sure it doesn't add any new vulnerabilities.
You might also consider running a anti-rootkit program such as rkhunter that will help you see if rootkits or other strange happenings are occurring on your server. RootkitRevealer is a comparable Windows program.
SELinux or AppArmor are very good at mitigating several forms of attacks on the server itself. Windows has something similar called EMET.

External Links

[1]: rkhunter official site
[2]: Windows Sysinternals site, where you will find RootkitRevealer among other useful programs.
[3]: SELinux wikipedia article. Check the References and See Also section.
[4]: A great article on Microsoft Technet detailing some very important security concepts. A good read no matter what OS you use.
[5]: Part 2 of the Microsoft Technet article above.
[6]: A thread from ServerFault which has yet more good information on recovery from an intrusion. Robert Moir's comment provide lots of good information.
[7]: An article on cert.org which details the steps one should take after a server compromise. It was written in 2000, so program specific information may be out-dated.

Using Moodle forum discussions:

Documentation