Starting with the trigger for redistribution, there are three circumstances for a redistribution of seats in the federal parliament in a state: 1) a change in the representation of the state in parliament (i.e. gaining or losing a seat); 2) an imbalance between the divisions of the state in terms of enrollment; or 3) the passage of time (seven years) since the last redistribution.
As noted above, because voters are required to be on the electoral rolls, the main criteria in drawing division lines are the number of voters enrolled in each division. At the time of the initial drawing of the lines, an individual division may not deviate by more than 10% from the average number of enrolled voters per division in the state. Furthermore, the committee drawing the districts is required to estimate the projected enrollment in each division in 3.5 years (the middle of the maximum life of a redistribution). No division may differ from the estimated average enrollment at that point by more than 3.5% (in other words, a large division has to be growing at a slower rate than the rest of the state and a smaller division has to be in a fast growing area). If at any point more than one-third of the divisions exceeds the average enrollment per division in a state for more than two months, the redistribution process is triggered.
Regardless of what event (national reallocation, lopsided divisions, or time) triggers the redistribution, a redistribution commission is formed composed of the national electoral commissioner, the chief federal elections officer in the state, the State Surveyor, and the State Auditor (all appointed, non-partisan civil servants). At the start of the process, the public has thirty days to provide written suggestions, followed by a fourteen day period in which individuals can comment on those written suggestions. The commission then publishes a proposed redistribution.
After the redistribution is published a second comment period begins with the public having 28 days to file objections to the proposal followed by 14 days in which the public can file written comments on the objections. The objections and the comments are then considered by an expanded redistribution committee (which includes the two part-time members of the Australian Electoral Commission) which then issues a final report containing the new division lines. In addition to the goal of achieving rough equality in terms of enrolled voters, the committees are charged with considering the existing division lines (i.e. minimize the number of voters changing division), the community of interests within an area, significant physical features (i.e. avoid a division divided by a mountain range or river), and the means of communication and transportation within a division (i.e. avoid divisions in which you the best route between one point of a division and another point is to go through another division). This system does not necessarily avoid lopsided districts (as in the US, inner cities tend to be more liberal than rural areas), but it does take the partisanship out of the line-drawing.
In theory, a redistribution caused by a change in the number of divisions per state should be easily completed before new elections (the process should take approximately 10 months or less). There are rules for temporarily combining or dividing divisions if an early election is called while such a redistribution is taking place.
Lastly, turning to the actual voting process. Australia permits early voting either in person or by mail for some reasons. Furthermore, on election day, while it is preferred that you vote at a polling place within your division (and only those votes are counted on election day), you can vote at any location in your home state or at any "interstate voting center" if you are outside your state on election day (which would also be a valid reason for casting an early vote). These rules are drastically different from the usual rule in the US where you must not only be in your actual district but at your actual registered polling location to cast a vote on election day. (For votes outside of a voter's division, some declarations need to be made that resemble provisional ballots in the U.S., but most of these votes are counted unlike in the US where there is a history of rejecting provisional ballots.)
The combination of mandatory voting and a voter-friendly system allowing a voter to cast a vote anywhere in their state with minimum hassle resulted in a turnout of 93% in the 2010 elections in Australia. (Note about 84% of the vote on election day is cast within the division with 10% by early voting and 6% on election day outside the voter's home division.)