  We consider strongly spin-orbit coupled double perovskites A$_2$BB'O$_6$ with
B' magnetic ions in either $d^1$ or $d^2$ electronic configuration and
non-magnetic B ions. We provide insights into several experimental puzzles,
such as the predominance of ferromagnetism in $d^1$ versus antiferromagnetism
in $d^2$ systems, the appearance of negative Curie-Weiss temperatures for
ferromagnetic materials, and the size of effective magnetic moments. We develop
and solve a microscopic model with both spin and orbital degrees of freedom
within the Mott insulating regime at finite temperature using mean field
theory. The interplay between anisotropic orbital degrees of freedom and
spin-orbit coupling results in complex ground states in both $d^1$ and $d^2$
systems. We show that the ordering of orbital degrees of freedom in $d^1$
systems results in coplanar canted ferromagnetic and 4-sublattice
antiferromagnetic structures. In $d^2$ systems we find additional colinear
antiferromagnetic and ferromagnetic phases not appearing in $d^1$ systems. At
finite temperatures, we find that orbital ordering driven by both superexchange
and Coulomb interactions may occur at much higher temperatures compared to
magnetic order and leads to distinct deviations from Curie-Weiss law.
