There is no real connection between them. We do not seem them physically cross paths while both are alive.
Melisandre is from Asshai and is worshipper of R'hllor. This following there are two gods, the god of fire/light (R'hllor) and the god of ice/darkness (the Great Other).
Syrio is from Bravos and seems to practice the religion of the Faceless Men. In that following there is only "one" god, the god of death (although he has many faces and as we learn from Jaqen the "red god" is one of them).
However there is a good reason that Melisandre knows words spoken between characters when no one else was around... she has visions in the flames! She can see events in the past, present, and future. While she doesn't always interpret them correctly there is no reason why she could not see these specific interactions and repeat a single line she heard.
[Melisandre] When I gaze into the flames, I can see through stone and earth, and find the truth within men's souls. I can speak to kings long dead and children not yet born, and watch the years and seasons flicker past, until the end of days.
[Jon] Are your fires never wrong?
[Melisandre] Never ... though we priests are mortal and sometimes err, mistaking this must come for this may come.
A Dance with Dragons, Chapter 3, Jon I