Our major airlines quality for what is called an "area AOC". That means they already have permission to operate ad hoc services to any port in Australia and in fact most other countries. All they need to do is an internal risk assessment specific to the new port and address any findings from that (e.g simulator sessions, maybe an on-site inspection), and share it with the regulator. This process can take as little as a few days if it's a simple well-established airport.
If they want to start new regular or RPT services, it's a little more complex in that they need to have a line maintenance facility at the new port, or contract another company to do it for them. This facility is inspected and approved by the regulator which can take a few months to arrange.
You also need government approvals to operate the route, both for the arrival country and overflight arrangements (though typically those are already in place from existing routes). Some countries can be a beaurocratic nightmare and take months to give this, others much quicker. Airports are similar, negotiating parking fees and reserving slots if required.
So to summarize, approval for a one off charter to a familiar port can usually be arranged within a week or two, a regular service needs a couple of months. Of course it can vary wildly depending in the scope of the operation, and I'm ignoring the sometimes years of economic research and monitoring that goes into deciding whether a route is even financially viable.