We demonstrate that optical spatial solitons with non-rectilinear trajectories can be made to propagate in a uniaxial dielectric with a transversely modulated orientation of the optic axis. Exploiting the reorientational nonlinearity of nematic liquid crystals and imposing a linear variation of the background alignment of the molecular director, we observe solitons whose trajectories have either a monotonic or a non-monotonic curvature in the observation plane of propagation, depending on either the synergistic or counteracting roles of wavefront distortion and birefringent walk-off, respectively. The observed effect is well modelled in the weakly nonlinear regime using momentum conservation of the self-collimated beams in the presence of the spatial nonlocality of the medium response. Since reorientational solitons can act as passive waveguides for other weak optical signals, these results introduce a wealth of possibilities for all-optical signal routing and light-induced photonic interconnects.