Studies of rotational relaxation dynamics provide particular insight into local solution structures and consequently into the interactions between species in a solution. We report here the results of molecular dynamics simulations describing a neat CO2 supercritical fluid and an infinitely dilute solution of toluene in supercritical CO2. Over a period of 0.1-0.2 ps, the rotation of the near-critical solvent molecules is relatively unhindered, becoming purely diffusive only on a time scale that is long compared with the decay of the orientational correlations. As expected, the rotational relaxation rate of a toluene molecule is found to increase with increasing solvent density, although the simulation results imply some anomalous behavior near the critical point that may be associated with the appearance of long-range spatial correlations. We also show that a system consisting of a nonpolar toluene analogue experiences an isotropic rotational friction environment, unlike the anisotropic environment in which a real toluene molecule is found when dissolved in supercritical CO2.