Go to the Medal Office in Castelia City. It is across the Gym on the 2nd floor. You get 2 Medals there:
- First Step - Participate in a Medal Rally.
- Rookie Medalist - Reach Rookie rank
Next time you speak to the Medal Guy that waits in the Pokemon Center, you will get your Medal Box upgraded to Rookie rank.
Then he tells you your next goal is 100 medals, and that is that.
Source: I did this yesterday.