The dynamics of partons, hadrons and strings in relativistic nucleus-nucleus collisions is analyzed within the novel Parton-Hadron-String Dynamics (PHSD) transport approach, which is based on a dynamical quasiparticle model for partons (DQPM) matched to reproduce recent lattice-QCD results - including the partonic equation of state - in thermodynamic equilibrium. The transition from partonic to hadronic degrees of freedom is described by covariant transition rates for the fusion of quark-antiquark pairs or three quarks (antiquarks), respectively, obeying flavor current-conservation, color neutrality as well as energy-momentum conservation. In order to explore the space-time regions of 'partonic matter' the PHSD approach is applied to nucleus-nucleus collisions from low SPS to to RHIC energies. Detailed comparisons are presented for hadronic rapidity spectra and transverse mass distributions. The traces of partonic interactions are found in particular in the ellitic flow of hadrons as well as in an approximate quark-number scaling at the top RHIC energy. Such a quark number scaling no longer holds at low SPS or FAIR energies.