The exciton relaxation dynamics of photoexcited electronic states in poly($p$-phenylenevinylene) (PPV) are theoretically investigated within a coarse-grained model, in which both the exciton and nuclear degrees of freedom are treated quantum mechanically. The Frenkel-Holstein Hamiltonian is used to describe the strong exciton-phonon coupling present in the system, while external damping of the internal nuclear degrees of freedom are accounted for by a Lindblad master equation. Numerically, the dynamics are computed using the time evolving block decimation (TEBD) and quantum jump trajectory techniques. The values of the model parameters physically relevant to polymer systems naturally lead to a separation of time scales, with the ultra-fast dynamics corresponding to energy transfer from the exciton to the internal phonon modes (i.e., the C-C bond oscillations), while the longer time dynamics correspond to damping of these phonon modes by the external dissipation. Associated with these time scales, we investigate the following processes that are indicative of the system relaxing onto the emissive chromophores of the polymer: 1) Exciton-polaron formation occurs on an ultra-fast time scale, with the associated exciton-phonon correlations present within half a vibrational time period of the C-C bond oscillations. 2) Exciton decoherence is driven by the decay in the vibrational overlaps associated with exciton-polaron formation, occurring on the same time scale. 3) Exciton density localization is driven by the external dissipation, arising from `wavefunction collapse occurring as a result of the system-environment interactions. Finally, we show how fluorescence anisotropy measurements can be used to investigate the exciton decoherence process during the relaxation dynamics.