Hey,
mit der nötigen Berufserfahrung und Qualifikationen ist es definitiv möglich eine Festanstellung oder einen Job abseits der gängigen Backpackerjobs zu finden. Es gehört jedoch jede Menge Eigeninitiative dazu, und du solltest deine Bewerbung und deinen CV genau auf die Stellenbeschreibung anpassen. Stellenangebote findest du z.B. hier: seek.com.au, gumtree.com.au und auf LinkedIn.
Visumstechnisch gibt es mehrere Optionen. Am einfachsten ist es z.B. zunächst auf dem Working Holiday Visum zu arbeiten. Auf diesem Visum darfst du jedoch nur bis zu sechs Monate für den selben Arbeitgeber tätig sein. Das 457 Visum/Sponsorhsip ist eines der gängigsten Arbeitsvisa, allerdings müssen hierfür von Arbeitgeber- und Arbeitnehmer gewisse Kriterien erfüllt werden. Neben dem ganzen „Papierkram“ kommt auf den Arbeitgeber außerdem einiges an Kosten zu. Informationen findest du auf der Seite vom Immigration Department
http://www.immi.gov.au.
Als Lektüre kann ich dir folgendes Buch empfehlen Bewerbungsratgeber Australien: Mit Strategie und Selbstmarketing zum Traumjob Down Under. Hier findest du eine Schritt-für-Schritt Anleitung für den Bewerbungsprozess in Australien und Informationen zu den verschiedenen Visa, sowie jede Menge Links und Kontaktdaten zu Recruitern, etc.
Viel Erfolg und nur nicht aufgeben!