Pienso que hay dos tipos: trabajo serio (desde que tienes tu permiso legal para trabajar en adelante) y trabajo “por debajo de la mesa” (cuando te pagan diario y no hay contrato de por medio).
Yo conseguí “trabajo serio” dos meses después de llegar (soy ingeniero informático). El resto de las personas allegadas que conozco tardó también dos meses en promedio. Sé de casos de trabajos por debajo de la mesa que han tardado apenas dos semanas en conseguir y les ayuda a costear gastos al inicio.
Todo depende qué tan necesitado estés por el dinero, qué estés dispuesto a hacer y qué tanto te dediques a buscar trabajo.