We present auto and hetero Bäcklund transformations of the nonholonomic Veselova system using standard divisor arithmetic on the hyperelliptic curve of genus two. As a by-product one gets two natural integrable systems on the cotangent bundle to the unit two-dimensional sphere whose additional integrals of motion are polynomials in the momenta of fourth order.