Ultimately, the "fastest" method is to use as many simultaneous methods to increase candy production as possible. So with that in mind, here are all possible methods of increasing candy production. Note this holds true for all Pokemon, not necessarily just Magikarp.
Catching
This will be the primary method of generating candies for your Pokemon, but there's some considerations here.
Spawn locations
As others have covered, common spawning areas for Magikarp are near real-world bodies of water - lakes, rivers, streams, oceans.
For an increased spawn chance, you also need to consider a popular spot: more Pokemon spawn when there's more people around. Look for spots with many Pokestops close by - usually parks, waterfronts or other popular locations.
Walk around
This is a very basic point, but worth mentioning - you will increase your chances of finding Pokemon by walking around the local area, as this increases the amount of area you see.
Lures and Incense
Use either a regular (Purple) lure, or if you have it, a Glacial lure, which will attract Ice and Water types, including Magikarp. Lure effects stack when on multiple nearby Pokestops, so that's another good reason to find a spot with many nearby Pokestops.
Likewise, Incense increases the chances of a Pokemon spawn based on the local spawn chances. If you're in an area that can spawn Magikarp, it should help. Incense also works better if you're walking around.
Pinap Berries
Feed wild Pokemon a Pinap berry before throwing Pokeballs. This doubles the candy of any caught Pokemon. For tier 1 Pokemon like Magikarp, this will result in moving from 3 to 6 candies per capture. This stacks with any timed research or other currently active event that increases catch candies, potentially netting you up to 12 candies per capture.
Transferring, Evolving, and Trading
Transferring a Pokemon to a Professor will give 1 candy. Likewise, evolving a Pokemon will give 1 candy - including if the evolution cost was 01.
When trading, Pokemon can give more candies based on the distance between the two Pokemon's catch locations. If the Pokemon were caught 100km or more apart, they will give 3 candies.
Buddies
Add a Pokemon as your buddy. As you walk around, your buddy will earn candies for their species. Magikarp and Gyarados earn 1 candy per 1km, so it's a pretty good trade-off.
Mega Evolving
When you have a Mega Evolved Pokemon, any Pokemon caught that shares a type with the Mega Pokemon will have a catch bonus of 1 extra candy. If your Mega Evolved Pokemon is at it's maximum Mega Level (30), this is increased to 2 extra candies per catch.
Community Days, Events and Timed Research
Keep an eye on announcements for upcoming community days, timed research, or themed events, which can both increase the spawn rates of featured Pokemon during those events, as well as double the amount of candy from catching them, depending on the event.
A Magikarp community day especially, will see a 3-hour window where 100% of wild spawns will be Magikarps (with increased shiny chances to boot).
Event Research Tasks
During events it's common for Pokestops to give research tasks specific to the event, with the completion reward being a Pokemon encounter. Generally speaking, Pokemon spawned from completing research tasks have better IVs - Attack, Defense, Speed stats).
Hatching
Hatching Pokemon from 2km eggs (the ones Magikarp are found in) results in 5-15 candies. Like events, the Pokemon available through Eggs changes occasionally, so Magikarp may not be available (and isn't, at the time of writing).
Rare Candies
Certain timed and special research, as well as raid battles, can drop Rare candies, which can be "used" on a Pokemon. Once used, the rare candies are converted to the Pokemon's candy type.
Feeding Gym Pokemon
Giving a gym Pokemon berries can very rarely drop a candy. Not a reliable source of candies, but if someone's dropped a Magikarp or Gyarados on a gym of your team colour, why not feed it a berry and try your luck?
1 For Pokemon that meet certain requirements, such as having been traded, their evolution cost is dropped to 0