Solids have solubility, just as liquids do. This is easily seen in metal alloys, where different amounts of different compounds can cause different crystal structure, low-level phase separation, and large-scale phase separation (if the solid solution is not stable). The changing of these nanostructures of the material can even occur with a material fully in the solid state, such as tempering of steel.
This relates to your question in that liquids freezing will behave very similarly with respect to phase composition as vapors condensing. The composition of the solid will be proportional to the composition of the liquid and affected by differing freezing points, just like you would expect from a liquid-vapor Txy diagram.
There are some differences, however. Molecules in solids can, as I said above, move around within the solid. However, this diffusion is substantially slower in solids than in liquids, and in non-metal solids, slow enough to be largely insignificant within the process of freezing. This means that the freezing process will create regions of differing composition within the solid. Further and related to this phenomena, the speed of freezing will impact the concentration of the solid, as faster freezing will push it even further from equilibrium.
The slow diffusion in solids also means that once trapped in the crystal structure, compounds with higher freezing points will not as easily exit the solid as they might from a liquid. This means that melting can behave very differently from vaporization, and solids might become a slush in the process of melting.
An explanation as to why this all occurs could go as follows: solubility is a factor of the strength of the interaction between different types of molecules. Those interactions must be stronger than interactions within the individual types to avoid phase separation. The process of freezing tends to not fundamentally shift the strength of these interactions. It is possible for materials partially soluble in liquid to be mostly insoluble in solid, but pairs of miscible liquids have such intense cross-compound interactions that freezing typically can only impact concentration of the separate phases.
The really important chemistry in this case takes place at the phase boundary between the solid and liquid, which behaves almost identically to that between a liquid and a gas. Molecules with weaker interactions with the solid phase (weaker interactions with other molecules in that phase) will tend to leave the solid phase more often - but there is an equilibrium where molecules will enter their less-favored phase. Essentially, everything you would have learned about liquids and vapors applies here, except diffusion is too slow to allow good mixing within the more condensed phase.
Of course, there are, in specific cases, more complicated explanations. One is of interstitial compounds, where a second compound might occupy spaces within a solid. While this happens to a degree in all solids, interstitials that are small enough to fit fully in a crystal structure without deforming it might exhibit unusual solid solution behavior, such as a compound with a lower freezing point showing a greater affinity for solid phase than the other compound.
To answer the title question, yes, separation depends on solubility. Unlike vapor distillation, though, it can also depend on temperature difference (thus speed) and mixing.
