However, not all airline staff will know about this and hence you should leave plenty of time for check-in and preferably, get an email confirmation from the airline in advance that this is acceptable.
Any DIAC office can do this, normally on a "walk-in" basis.
If the old passport was lost or stolen, it might take a few days to get a new label.
Unless the visa is a Resident Return Visa (subclass 155 or 157) there is no charge - see current form 990i. Some DIAC officers will try to apply a charge and you should speak to a supervisor/manager if this happens.
If offshore, you will need to check the local procedure. Some DIAC offices offshore may not want to re-stamp however they have to do so if the old visa label was lost or stolen.