A government agency sent our website admin an email that our website had been defaced

It's extremely easy to fake email. If someone did fake this, I don't see how the agency would know about it. The concern is that the link they sent you was the attack itself. For example, this could be a CSRF attack:

With a little help of social engineering (such as sending a link via email or chat), an attacker may trick the users of a web application into executing actions of the attacker's choosing.

One suggestion is to contact the office and find out if this is something they do. Just because the language seems right and says it's from the right sender means nothing. That's a common approach used in phishing emails.

A CERT (Computer Emergency Response Team) task is precisely to watch over the security problems on the actives under their constituency.

In the case of national CERTs like CERT-AU, they often care about everything hosted on their country, and if they are made aware of any issue, their task would be to contact with the affected owner so that he can fix the issue (as they did in this case). They could also have provided you some advice in case you had needed it to find the issue.

These services are free for the people (they are a governmental agency), and they won't ask you for any kind of payment for having notified you.

A full list of CERT-AU services is available at https://cert.gov.au/services

­­­ 

The way of providing you the url as hXXp://domain.com[.]au/s.htm is a quite common one of sharing malicious urls. The goal is that you receive the url (which you will need in order to find out where the malicious content is) but at the same time minimise the risk that you could inadvertently open it in the wrong environment or before reading the email in full (additionally, it also helps avoiding email filters that delete emails containing malicious urls¹).

­­­ 

There are many sources from which they may have learn about this incident:

• An individual notified them
• Another CERT or security company notified them
• It appeared on some list of compromised sites they subscribed to
• It appeared on some defacement forum they were watching (like zone-h)
• They found it while performing some other investigation

­­­ 

Amongst the benefits of sending the notifications through the CERT are:

• When there are multiple compromised sites, it's much easier to notify a single entity per country than to each website operator¹
• The CERT will often have some procedure about retrying in case he was ignored by the admin. A third party would probably just attempt it once.
• The CERT may have better contacts to send the notification to.
• As a neutral party, the CERT is more likely to be payed attention to²
• No language barrier: the CERT should be able to contact the website owner in his mother tongue.
• The CERT will have technical people able to easily understand the issue, and able to explain that, if needed, to the website owner (which may have zero knowledge itself).

­­­ 

A list of worldwide CERTs (both public and private) is available at First: https://first.org/members/teams 

A database of European CERTs and security teams is also available at Trusted Introducer.

­­­ 

¹ For instance, Google finds loads of malicious urls every day that it finds through their crawling, instead of attempting to report them directly to the owner, they share them with the relevant national CERT so that he can take care of the notification.

² Just imagine this question being «a random guy from a hotmail address sent our admin…»

Unless they told you in the letter, there is no way of knowing how they were informed of the hack. The chances are that someone reported a problem, attack, or probe of some kind to CERT, and they were then able to trace the origin of the back to your server's IP address.

I recommend you at least continue your investigation; but consider engaging a security firm. There's a lot to do at this stage of an attack besides understand what happened. You may need to preserve evidence, you'll need to recover your systems, you may need to provide breach notifications, you may need your clientele to change their passwords; all kinds of activity can stem from a breach, and a professional will help guide you through it all.