Is such an orbit possible that allows a satellite on Earth and another on Mars to always be in direct line-of-sight? If not always, how much "most of the time" could it get?
Or would a multi-satellites setup be more suited?
 A: Yes, but the satellite(s) would be orbiting the sun instead of the earth. You place a satellite at either L4 or L5 Langrangian points on the Earth-Sun two-body system--these are points 60 degrees to either side of earth on her orbital plane around the sun where you can place a satellite. Throughout earth's entire orbit the satellite will maintain that 60 degree separation, even under the influence of earth's gravity. It does this by moving slightly faster than earth (tangential velocity) at a slightly larger orbit than earth, allowing the angular velocity to be equal to earth.
With the satellite in L4 or L5, mars will always be in line of sight to either earth or that satellite. You can add more satellites such as geostationary ones on both planets to allow to specific points on those planets to have line of sight 100% of the time. 

A: The best way to minimise loss of sight would be to have the satellites orbiting at a very high altitude, e.g. beyond the distance of the moon. It would then be very rare for the satellites to be eclipsed by the planets, or moon. Such eclipses could also be easily avoided with a small orbit correction or by synchronizing the orbit in such a way that potential eclipses never happen
The only case where you would be caught out would be when Mars passed behind the Sun as seen from Earth but such events are very rare. If the orbits were higher than the radius of the Sun (700 Mm) it would be possible to avoid even the Sun occultations with careful planning and some orbit adjustment.  
If the satellites have to be nearer their planets you could keep them orbiting around the axis joining the planets so they are always in sight, but more fuel would be required to keep them in those orbits as the planets move.
