Fishing Leveling Guide
First of all, visit any trainer in the main cities of old Azeroth - just ask a guard, and learn Fishing Apprentice.
1 - 300
Buy a Fishing Pole, it's sold by Trade Goods vendors and Fishing Suppliers. Go to the nearest body of water, and fish from skill 1 to 300. When you reach skill 75, you can go to The Barrens and catch [Deviate Fish]. The best spot is to go into Wailing Caverns and fish there, because then you won't have to move between pools to find School of Deviate Fish. You can sell the fish raw at the Auction House or if you have the recipe you can sell [Savory Deviate Delight].
Do not forget to visit your fishing trainer when you reach skill 75, 150 and 225!
300 - 450
Before you travel, gather together gear and lures that improve your effective fishing skill. Take at least a +5 Strong Fishing Pole and a stack of +75 Bright Baubles.
Go to Borean Tundra in Northrend and learn Master rank from Fishy Ser'ji (Horde) in Warsong Hold, or Old Man Robert (Alliance) in Valiance Keep. Even with good gear and lures, initially you will catch a lot of junk fish in Northrend. In Borean Tundra you will need 475 effective skill to fish without catching junk. If you are higher level, around 80, you should go to Wintergasp instead of Borean Tundra, you can make the most gold by fishing there, at the start, around half of your catches will be junk, but the amount of junk will gradually decline.
Do not forget to visit your fishing trainer when you reach Fishing skill 375!