Rematches are determined by three things. One, if you have registered them in the Pokenav, Two, If you have obtained the 5th Gym badge, and Three, if you have walked a lot.
Regular Trainers are eligible for rematches after obtaining the Balance Badge; once it is obtained, if the player is on a map with eligible Trainers, each Trainer on the map has a separate 31% chance to demand a rematch every 255 steps.
You can check Serebii for the rematch teams of each trainer.
Source: Bulbapedia
Hope I helped.
