They will send SMS
Previous communications, such as the shutdown of the 3GIS network it purchased from 3, was done over SMS to affected phone services and this will be no different.
Also, Telstra's 3G network maps tend to be a bit conservative. A "blue tick" phone (that is one recommended for rural coverage) can often get reception on areas where the map shows they should have none.
There are not very many areas where 2G at 900mhtz works but 3G at 850mhtz does not. For the less than 0.5% of the population that might apply to, a few extra towers can be built, or new antennas added to existing sites.
This shutdown is nowhere near as significant as the shut down of CDMA was, or the shut down of AMPS (analogue) before that.
There is a 3rd option not mentioned in the article - those affected could move to Optus. Optus has the largest 2G network in Australia - it is geographically much bigger than Telstra's because since 2005 Telstra has been pouring all new money into 3G and Telstra's 3G network now covers over 2.3 million square kilometres.