Be sure to use the right bait. The fishing guild master should've told you what bait to use. Use as much gear with perception as you can. It's all rng, though. I was nearly level 10 by the time I completed the "catch three sardines" quest.