You earn medals by participating in Tours on Tortimer's Island. You can either do this solo, with friends, or through random matchmaking through the Internet.
The number of medals you are awarded is dependent on how well you do in each minigame. The better your performance, the more medals are rewarded. There are also 3 difficulties, from 1-3 stars, and the higher the difficulty, the more medals you earn.
For example, during the Easy Hammer Tour (1 star), I hit the machine 91 times, which gave me a Gold Tortimer award (these are bronze/silver/gold and aren't tangible, just an award to judge how well you did) and 6 medals. During the Level-Up Hammer Tour (2 stars), I hit the machine 80 times, which gave me a Gold Tortimer award and 8 medals.
In addition, when playing with multiple people, you earn Bonus Medals based on how well you did in comparison to them. The way the games work is that they are a mix of cooperative and competitive. You all have to do something that works towards a collective goal, but you do get bonuses based on how well you did. So, again using the Hammer Tour as an example, you have to hit the machine 30 times within 3 minutes. Each person's hit would go towards the total, but at the end, they would also get bonus medals for how many times they hit it.
Once you earn 50 medals, you can earn membership to "Club Tortimer", which allows you to participate in Tours with random people on the Internet. If you're not a member, you can only go on Tours with people with whom you are friends. This is handy if you don't have friends that you can play with or they're on at times when you're not available, etc.
In conclusion, the fastest way to earn medals is by playing with multiple people as opposed to solo, and playing on higher rather than lower difficulties (and performing well, to boot).