Is it legal in Australia to publish letters and emails sent to me by a lawyer on behalf of their Client?
There are several issues potentially involved in publishing such letters. If the recipient has signed an NDA or is under some other sort of individual duty of confidentiality, s/he should normally not publish the letters or disclose their contents, and if s/he does so there will usually be some sort of penalty possible. But in some cases this may not apply. For example, the duty to report a crime will generally supersede a private NDA. So-called "whistle-blower" laws may give additional protection to disclosures when they apply.
If the letter is protected by Government secrecy classification or some other government regulation, disclosure of the contents may carry a penalty. But this may not always apply. For example, consider the case of New York Times Co. v. United States, 403 U.S. 713 (1971), known as the Pentagon Papers case. According to the Wikipedia article:
The question before the court was whether the constitutional freedom of the press, guaranteed by the First Amendment, was subordinate to a claimed need of the executive branch of government to maintain the secrecy of information. The Supreme Court ruled that the First Amendment did protect the right of The New York Times to print the materials.
However, an ordinary letter from a private lawyer will not involve Free Press issues.
It is also the case that a letter, like any other modern original writing, is protected by copyright. To publish the letter without permission might be a copyright infringement (unless one of the exceptions to copyright applies) and an infringement suit might be filed. But usually the would be little or no economic value to such a letter, and so little or no damages available in a copyright suit. This might mean that such a suit would not be effective in deterring or dealing with such a publication.
If the recipient reports on the contents of the letter without actually copying it in the report, there would be no plausible copyright issue and the device of an infringement suit would not be available.
You shouldn't publish the letters if you are not supposed to have them, but if you rightfully have the letters you should be able to publish them unless you signed an NDA or there are government secrets or something you can't publish in them, but just coming from a lawyer does not mean you can't publish them.