Public support for policies that address climate change, in Australia and elsewhere, has become polarised, and has declined in Australia. The polarisation and decline has occurred despite considerable efforts by government, non-government and scientific bodies to raise levels of support. In this research, therefore, we aim to better understand the preferences of politically salient household segments with the objective of more effectively communicating to those segments the desirability of addressing climate change. Replicating an American market segmentation study, we find that 26% of participants fell into the most politically salient household segment, labelled Cautious. This segment is relatively open to changing its views about climate change, and is supportive of both government and opposition policies. These findings suggest that segment members will potentially be influenced by targeted media campaigns by either side of politics. Additional findings relate to effective communication channels, and trusted sources including the use of celebrities.