The problem of the existence of an additional (independent on the energy) first integral, of a geodesic (or magnetic geodesic) flow, which is polynomial in momenta is studied. The relation of this problem to the existence of nontrivial solutions of stationary dispersionless limits of two-dimensional soliton equations is demonstrated. The nonexistence of an additional quadratic first integral is established for certain classes of magnetic geodesic flows.