There is a degree of trial and error I've found.
Most of the lures will tell you what type of fish they work best with. So you can couple this with the map to get an idea of what you should be using.
So if you're in Cleign and you have a lure for Cleign Bass for example, safe bet that's a good place to start. Plus if you're fishing in the ocean, try lures which attract 'Sea Bass' and similar.
Also, it's worth scouting the local area, quite often there is fishing tackle laying around, you can pick up, which also helps give you a clue as to which lure to try first.
However it's worth noting that you can catch fish with the 'incorrect' lure, it's just harder to get a bite.
"Perhaps you should respool your line Noct?"
Or check this guide for some extra information. I've quoted the relevant section below.
Lures : There’s lots of lures in the game. You’ll need to swap out which lure you use based on what fish you’re hoping to hook and where. Popper lures let you seek fish near the surface, pencil lures let you fish more effectively at dawn or dusk, swisher lures make boring fishing spots more lively, crankbait lures help you in rocky or littered waters, minnow lures work in clear waters, and vibration lures are best for wide areas.
Lure Weight : The heavier the lure, the deeper underwater it goes, and the bigger the fish it catches.
Lure Color : Fish like colors close to their own. Get a red lure for a red fish.
There are many lure possibilities, but pick the one best for the environment you’re hoping to catch the fish.
Lines: With only three types of line, you’ll mostly be purchasing these from shops. The higher the durability, the longer it can hold out against tension (aka damage) inflicted by fish.
Rods: Rods provide defense, which determines how much tension damage on your line they cancel out. You can get better rods from shops and by completing sidequests for Nayth.
Reels: Reels determine how fast you knock out a fish’s stamina bar as you reel it in - basically your fish attack stat. Tackle shops have high-quality reels, but the very best reel is called Llymlaen and is a reward in the Totomostro mini-game.