Salut,
Pour ma part, sur Auckland, j'ai trouvé du taf de 2 façons :
1. Via le bouche à oreille. Un pote rencontré sur place m'avait parlé de l'agence d'interim qui l'embauchait et m'avait présenté sur place. Bon au final, c'était une agence spécialisée dans la construction. J'ai tenu 15 jours avant de laisser tomber (principalement le fait que c'était bien physique et que tu dois te pointer tous les matins à 6h30 à l'agence sans savoir si tu allais avoir du boulot pour la journée).
2. Via le porte à porte. J'ai déposé quelques CV dans des restos/bars qui me paraissaient sympa. Au bout d'une dizaine de CV, un manager m'a pris direct en entretien, essai le lendemain et embauché 2 jours + tard

Un petit conseil : si tu vises la restauration/hôtellerie, ne vas pas déposer de CV le Samedi/Dimanche, c'est une perte de temps. Les managers sont soient pas là, soient trop occupés pour y prêter attention.
Pour la recherche à distance, ça ne vaut la peine que si tu as des qualifications qui sont recherchés sur place (ingénieur, plombier, soudeur, etc...).