The bureau of meteorology has monthly cloudyness charts
http://www.bom.gov.au/jsp/ncc/climat...eriod=mar#maps
Lowest mean cloud amount at that time of year is central east South Australia. The Flinders Ranges lie in this region. They are relatively expensive to stay in but have great skies.
Wilpena Pound (Flinders Ranges)
Arkaroola ( Gammon Ranges )
Cheaper would be to find a small motel or farmstay in or near small towns in eastern South Australia such as Hawker. Depending how long you stay, it might pay to hire a camper so you can stay in National Parks depending on approval from the "CEO."
Joe