The Tsar Bomba's fireball did not significantly mix with soil or debris (it was technically detonated low-enough that normally one would expect it to have, but the reflection of the shockwave on the fireball "bounced" it upwards, and actually kept it from touching the ground, as you can see in the footage of it). As a result the cloud stayed high and light. It fell out of the cloud only over a fairly long period of time (some of it would have fallen within hours, but a lot of it stayed up there weeks, even months). This means that it covered an immense area in the northern hemisphere, but the actual fallout was relatively diffuse. This kind of fallout deposition is called "global fallout," to contrast with the "local fallout" that one associates with surface or near-surface bursts (the sort that produces long plumes of contamination).

It should also be noted that the Tsar Bomba had an intentionally extremely low fission fraction (3% or so), so in terms of its fallout radioactivity it was more akin to a 3 megaton bomb (assuming a normal fission fraction of 50%) than a 50 megaton one. So its fallout was considerably less radioactive than the 1954 Castle Bravo test (which had 10 megatons fission yield).

Which is to say, in the TLDR version: it went into the air, and from there, over time, onto sea and land, but over a vast area so that no specific location was appreciably contaminated.