In previous games, to get rematches with trainers, you used the VS Seeker to see if the trainers were willing to battle. In HeartGold & SoulSilver however, the rematches are done a different way. Firstly, only a few dozen trainers in Kanto & Johto are capable of being battled again.
In order to get the rematch, you have to receive the PokéGear number from the trainer in question. Then, on a certain day, you will need to ring that trainer in question to organise a rematch. It is not guaranteed that a rematch will be discussed when you call but keep trying and you should get it.
You can navigate between each day here and it will show you all the rematches you can do in each day as well as each team for each trainer