We report measurements of the magnetoresistance in the charge density wave (CDW) state of rare-earth tritellurides, namely TbTe$_3$ and HoTe$_3$. The magnetic field dependence of magnetoresistance exhibits a temperature dependent crossover between a conventional quadratic law at high $T$ and low $B$ and an unusual linear dependence at low $T$ and high $B$. We present a quite general model to explain the linear magnetoresistance taking into account the strong scattering of quasiparticles on CDW fluctuations in the vicinity of hot spots of the Fermi surface (FS) where the FS reconstruction is the strongest.