也≒also, too ..
都≒both, all ..
if you only say 他們也都是墨西哥人
that means either you or the person you are talking to is Mexican.
他們也都是墨西哥人
this sentence means someone is 墨西哥人 and "all of them" are "also" 墨西哥人
也→someone and them
都→all of them
we only use 也都 on this situation for unclear reasons
I think it's because
you speak from your perspective, so you should start with the fact that is closer to you. like you or the person you are talking to is Mexican.
I won't say 都也 is wrong. it's understandable.
just not what we usually would say.