To catch a legendary fish, you don't need to be any level but since of a update, buy legendary lures, and rent a fishing boat. Despite the stories told by fishing masters, all legendary fish can be found anywhere on the map.
Once on a fishing boat, put a Legendary Lure on your line and make sure it sinks as far as it can go. The skill "Sink Lure" is useful for this. If you don't see vegetation at the bottom of the screen, you are not deep enough. Once near the bottom, wait for a while. Make sure you scare away any fish that come near. It could take up to 10 minutes of waiting, but a legendary fish should eventually appear.
Once a legendary fish takes the bait, you will have to do a little minigame to reel it in. This works in three phases: Struggle, Reel and Catch. The game will usually alternate between "reel" and "struggle", with an occasional "catch".
Struggle - Quickly left-click as fast as you can to keep it from getting away.
Reel - Move the mouse in a clock-wise circle around the reel to crank it closer.
Catch - This happens occasionally. Quickly click on the back-spinning reel to keep from losing it.
The different parts of the reeling game can be harder or easier depending on the fish - for example, "struggle" is difficult when catching Mossy Moses, while "catch" is difficult when catching Speedy Lou.