As said, no onscreen evidence. Thus, enter my interpretation:
A long time ago in caves of planet Trill, slimy creatures roamed the dark subterranean waterways and used electric pulses both to stun their prey, and to communicate with their own kind. A bit shorter a time ago, they had gotten very good at both stunning and communicating - and had begun, more or less accidentally at first, to communicate with their victims rather than just with their own kind. They eventually learned how to use the pulses for luring their prey in - and, later, for controlling their prey. In essence, they could "possess" more advanced creatures. Eventually, this path of evolution allowed them to refine the possession into complete bodily control, and now they were free to leave their fetid underground pools and start preying on creatures of the dry land...
Perhaps their victims included primitive apes, which then evolved into humanlike creatures - while the Trills evolved apace, constantly capturing a small portion of the ape-human population, and eventually becoming a biological fixture of the ape-human culture. They did little harm to their human hosts, as they were more valuable when used as hunting bodies than when used as food.
Or perhaps there were no apes on planet Trill originally, but the Trills were able to hone their possession skills on other species, so that when the first spacefaring humanoids arrived on the planet, they fell prey to these master hunters.
Either way, the Trills would now be in control, at least in control of small population groups. And now they would launch into a propaganda war: the population they controlled would start spreading the gospel that said the Trills were friendly and indeed beneficial, and that everybody should try one.
Eventually, this would indeed catch on, as the Trill promises were not completely empty ones. The ability to carry memories from generation to generation would exist for real. The story about the possession being "benevolent" would mostly be fabrication, though; most hosts would be under strict control, and strictly controlled to tell everybody that they were free.
All sorts of hosts would be compatible with the Trill, but they would soon develop a preference towards certain "easy" species. The spotted species typically associated with the Trills would be a favorite, for having that nice pouch on the tummy and thus requiring little in the way of surgery or violent burrowing... Regulation of the "market" would be important, though, and so all sorts of propaganda would emerge on this "compatibility issue".
The Trills would still breed the old-fashioned way, in the pools. But otherwise, they'd abandon most of their original ways, and would take nourishment not through hunting, but through very modest tapping of the gastrointestinal system of the host. They'd also become quite intelligent and civilized - and whatever they lacked in education, they could coerce out of their hosts' educations.