How does this work? Remember that all events are quantum-mechanical in origin: around every definite event there is a quantum "fog" of other possibilities, only one of which turns into reality. The universe simply ensures that only self-consistent events turn into reality: killing your father is just one of a great number of possible outcomes which never become real.
This is a danger for the time-traveler, because it means that when a seeming paradox is immanent, otherwise unlikely events may become probable to prevent the paradox from happening... if both heads and tails lead to a paradox, then the coin is forced to land on its edge instead, collapsing the quantum wavefunction in a way which would be very rare usually. This means that in the vicinity of a time traveler, probabilities are often twisted. For the traveler himself, this is especially dangerous, since the possibility for paradox can be easily resolved by having a piano drop on you before you attempt to kill your father.
This self-consistency often leads to the prevention of the creation of the time machine itself, which is why time travelers are so rare.
The interactions between parallel timelines are poorly understood. In many cases, rather than evolving independently, resonances between "close" timelines will cause them to be nearly identical up to some crucial event in history, which goes one way in one universe and another way in the other, after which the connection between them is mostly broken.
Travel between parallel worlds is not usually as dangerous as travel within your own timeline, since paradoxes are harder to create (for instance, having two travellers from different periods in the same timeline come to the same point on another world and talk to each other). And in most cases, the paradox prevention can act in subtle ways, causing you to "miss" your desired timeline slightly and end up in another one which is mostly identical but does not have the same potential for paradox. This is often the fate of time travelers: they aim to go back in time within their own timeline, but instead arrive at a minutely different parallel world where their actions have no effect in their own present time.
This difference led to a quicker evolution on Naliata's world, since the creatures were able to tweak the laws of physics slightly to their own advantage. Instead of four billion years on our Earth to go from the simplest bacteria to humans, her world evolved intelligent life in only one billion years, and many species of it as well. This means that to come here, she travels forward in time three billion years as well as moving to a different timeline.
Naliata's superficial similarity to a human woman is due to Staewin's search through many parallel worlds: after discarding many possibilities, he eventually found one -- ours -- with an intelligent species on Earth which was similar enough to his own for him to blend in without suspicion. The similarities are only superficial, though: Naliata's biochemistry and internal anatomy are fairly distinct from humans, and there is no possibility of genetic compatibility.
The mechanism used to transfer a person from one timeline to another is to not move their physical bodies, but only the pattern of it. That is, a chunk of matter on the other side (dirt, whatever) is reformed into the person, while their original bodies are likewise transformed. This is done because it is very hard for extra matter to suddenly pop into being in a universe, but it is "merely" extraordinarily unlikely for a clump of dirt to spontaneously reform itself into a person.
This is a fairly delicate procedure, as might be imagined, and is generally beyond the ability of normal mages to perform. Instead, this part of the process is done by an e'crailh partner. The e'crailh are a species of amphibious cephalopods which possess a natural short-range teleport ability which functions along similar lines: transferring their pattern a short distance away to escape predators. With suitable training, they can facilitate the transfer of a pattern from one timeline to another using the same instinctual mechanism.
So a mage and an e'crailh together can transfer themselves between timelines. This technique is not very well known, and might be dangerous were it well-known due to the possibility for paradox.
The other is Naliata's connection. She was originally intending to make use of "her" Staewin's original connection, which would have put her in the vicinity of the year 2200, but missed slightly and ended up around the year 2000 instead, in a different timeline: the inn's.