I learned fishing on my way out of darnassus but never used it.
One day i was sneaking around elywnn forest pick pocketing defias and i found a hidden house up in the hills. It had a chest so i killed the defias there and looted the chest and got some cooked fish. Then i remembered i had fishing so i walked out onto the dock and fished for about 20 minutes. Then it started raining.
Almost no one knows about Thunder Falls and it's where i leveled my fishing up to around 110 instead of in SW canals.