Virgin took on cadets last year...
To answer your question, having work experience in any area where you can demonstrate teamwork, leadership, good communication and customer service skills will put you in good stead for any airline cadetship a, let alone Qantas or Virgin.