Sydney and Melbourne are where nearly all of the ID jobs are located, so it’s likely that you will be living in one of them. Jobs aren’t always posted, so it’s worth sending through a tentative CV and folio. Most design firms that post an ad seem to do it themselves, while most of the work found through recruitment companies seems to be packaging and retail displays.
I’d make a small note in it about your working holiday visa, as I’m quite sure that you are only allowed up to 6 months with any given employer.
Are you going for any specific industry?
I don’t know where you are currently living, but it gets warm here in summer! 