Now, if the aliens were sending us transmissions through circularly polarized waveforms that would be different, that's a matter of observation rather than communication.
Now, there is a phenomenon where if some particles decay in a magnetic field the products tend to have their products go in different directions depending on the magnetic field. This was a bit of a shock since physicists had assumed left-right symmetry until then. http://en.wikipedia.org/wiki/Asymmetry
Using some form of symmetry breaking works too but is a much worse solution from an engineering perspective since the circular polarization is so much simpler and more direct. But it would work.
http://en.wikipedia.org/wiki/Parity_violation#Parity_violati...
Now, the weak force is pretty weak, so you usually have to do sensitive experiments to isolate it. But it's conceivable that there is macroscopic evidence of parity violation sitting around the cosmos which don't require common observation, e.g. maybe black holes have a slight statistical preference for clockwise vs. counter-clockwise jets. (Ultimately, such evidence would have to be traceable back to the weak force.) I'm not sure.
Once that commonality is established we can start to explain to them the everyday concept of symmetry and how we give different names to different directions of symmetry.
Of course, that is assuming that they don't exist in some sort of weird bubble of the universe that operates with antimatter instead of regular matter (and is therefore using some mysterious positron-based "electricity"). I suppose if that were the case, our rendezvous would be disastrous anyway, so destruction of the gate would probably be the best possible outcome...