"All our relatives live in Canada."
It can, but it typically doesn't.
Indeed, often the place precedes the action if the action occurs in the place (e.g. "我在加拿大工作"), whereas if the location is the result of the action, it comes later.
As for "住", to put it simply, for a verb of "positioning", if I can call it that, the "在" phrase typically comes after the verb, and for the sake of simplicity, you can think of "住" as a verb of positioning, just like "放", "坐", "站", "待", "躺", etc.
This is subject to any sort of structural change in emphasis that might be possible or necessary, which is why you get, for example, "我们的亲戚都住在加拿大" but "我在加拿大住了两年了".
Right. You have to include the notion of "all" in your translation, since it occurs in the English.