Don't even bother trying without a mount, unless you're on a pvp server and are willing to throw lots of money at the problem.
Here's a brief and unformatted rundown of how to win:
If you're a shaman, buy a buttload of fish oil.
If you can twobox a shaman, buy twice as much.
Bind yourself at the Bootybay inn, near the door as you can manage. Before the contest starts. Be sure your hearth cooldown will be available 15 minutes after the contest begins.
Proceed to typically desolate areas during the fishing contest. My favorite place is the troll island to the northwest, Yojimba.
Equip your riding crop or equivalent. If you lack waterwalking superiority, equip master angler's hook or swiming belt. And your fishing pole, with lures handy.
Mount up. On your fast mount. Be on the lookout for other competitors while you wait for the contest to begin.
Race around the island and empty those fishing holes. Speed is of the essence, you want to catch at least one fish every 30 seconds on average. Yes, expect the contest to be over within 20 minutes. Find your hole, empty your hole, mount up immediately and move on to the next one. The only reason to not mount up is if you have an instant travel form and th next hole is less than 4 seconds away in that travel form. If you come across someone at a fishing hole, keep moving. Unless you can kill them.
If you're operating out of Yojimba, you will circle the island. There will come a time when there are no fishing holes there, head north and follow that stretch of shore looking for more holes. There are about three possibles there. Now, if there are still none there you can head east. I don't do this unless I only need about three more to win, and there are no fishing holes in sight. If you have waterwalking, put it to use.
Do not waste time on holes you cannot reliably hit with your hook.
I keep two empty slots in my main pack, and have a tasty fish in each, so I can tell at a glance how many more fish I need.
Count the fish you pull out of each hole. There can be, I believe, between 3 and 5 successful catches. (Correct me if I'm wrong, it's been a while.) If you've only cast a line once when some bugger slides up to use that hole, mount up and move on. After killing him. If you've caught four fish from that hole and have cast your 5th line before he cast, stay there and finish it. Chances are you'll get that last fish.
Ideally, you want to stand where you can promptly mount after emptying the hole.
As soon as you have your 40th fish, you gate back to BB and turn them in to the goblin. Know what you want ahead of time, you don't know if some bugger is right on your heels with his 40. If you dither, he may win.
Bring friends. A couple friends can protect you, your other friends can patrol the rest of the shore harassing other anglers. I did say lots of friends, right? Pay them if you need more friends. They don't have to kill other anglers, just slow them down. When I would run this duty on my shaman, I'd drop a searing totem and keep moving. Pet classes can sick their pets and keep moving, toss dots, etcetera. The goal is to stop the other anglers from getting 1 fish every 30 seconds.
Cross faction PVP:
Money buys friends. Hire people of the other faction to harass everybody but you and your escort. You'll need to provide names, of course.
Dealing with friends who are competing:
Set up your own fishing cabal. You gather people who are interested in winning, you form a group. Draw lots for the order of "winning." The goal of the non-winners in any given week is to slow down other anglers by fishing out of their holes or killing them, or providing protection to the winner. This requires trust, non-winners may be inclined to free-load when they're not actually up to win. In this case, kill them.