We never specifically learn why Xehanort knows about the 'Other Side'. It's a somewhat safe assumption that the only way he could know is by watching other subjects being sent all over the world, and noting that some landed outside, unable to return.
It's also possible that the reason he concluded that sending the princess out would lead him to the Keyblade is that the individuals sent out went to something they were connected to instead of Traverse town, which I suspect he saw many of his subjects go to.
The only major issue I see is, what could these subjects possibly be connected to outside the world? I suspect that anyone could be connected to anything under the 'one sky' they all share. I think it's unlikely that the sky is shared outside the world though.