Para esas empresas te pedirán la titulación de buceo (da igual media o pequeña profundidad, y de la comunidad autonoma no importa). Se recomienda que tengas experiencia en emisarios (colocación y/o estabilización). Pero lo más importante es que poseas: Formación Básica (normalmente de 2-3 semanas, creo que la equivalencia en el extranjero es el "Basic Safety Training STCW 95") y además el Marinero pescador (conocido anteriormente como Certificado de competencia de marinero, 1 semana de duración).
En cuanto a la compañía investiga llamando a los listados de esta web, ANEBP, marabajo, etc... (algunos correos o télefonos no corresponderán) que seguro así o por medios de tus contactos (si te lo quieren decir, cada cual que proteja sus intereses) podrás averiguarlo.