1-5: Limsa lominsa. using the bait provided
5-10: Middle la Noscea. Nym river switching up to Crayfish Balls
10-20: Western la Noscea Brewers Beacon using goby balls until 15 where you switch to rat tails
20-27: Upper la Noscea. Oakwood Lake on the western side of the map using Crow Flys and Brass spoon lures
27-35: Western Thanalan. Moondrip using chocobo fly here gives you grip killifish which are the best exp by far until dune fishing
35-40: Southern Thanalan. Sagoli Dunes using Sand leeches
40-45: Eastern Thanalan. The Burning wall using Stem borers until 41 where i switched to Mithril spoon lure
45-50: Either Cloud Fishing in Coerthas or Mor dhona North Silvertear for catching fish for the nearby leves (HQ fish turn ins are 90k a pop) Cloud fishing uses hover worms, Mor Dhona used Glow worms.
and welcome to 50 fishing!

PS: If you want to make money, you can start fishing Red Coral at Lv37 using Sinking Minnow in Western La Noscea among the beastmans!