During the Beta I had every intention of writing about Fishing, but I got sidetracked by a significant change in the skill-up ratio. After one particular patch, I was getting skill points every 4-5 catches and I went from 375 to 450 in just a few hours. I went to El's web site to see if others were experiencing the same thing, but I was the first to post about it. Within a few days the change was confirmed and it persisted through the rest of Beta. Still, no one was certain if this was a permanent change.
Now it seems we have our answer. On the Live server I've leveled to about 390 Fishing and I'm skilling up every 10-12 catches. While this is certainly better than where we left off in Outland, it's not quite as exciting as the changes we were hoping for. I haven't investigated this myself, but if you're curious about how the existing leveling progression affects lower tiers of Fishing, I'm sure El has the skinny on that :)
There's not really much I can say about how to level Fishing, there's not a whole lot of mystery in throwing a line a few hundred times and looting the fishies at the other end. What I'd like to toss out instead are some things you might want to consider in conjunction with your fishing efforts. There's no compelling reason to level Fishing just for the points, but there are a number of new Achievements for Fishing. For those planning to level Cooking, I would definitely focus on that and ignore the skill points. In all likelihood you'll cap before you collect all the fish you need to cook, so don't waste your time on random fishing. Between all the various Northrend Fishing achievements and Cooking, you should have no trouble reaching 450 without even trying.
I would also encourage you to bring plenty of lures with you when you leave your home city on a fishing expedition. Since Northrend is all new, you won't know where to find lures in an emergency outage. Trust me, I ran into this in the Beta when I headed off to fish and realized I didn't have my lures. Then I tried to figure out where I could score some and I just didn't know any of the vendors/zones well enough to find supplies. So take care of this before you're in the middle of the Frozen Sea, surrounded by penguins!
I'd also like to share a few helpful hints for certain kinds of fish. For the Small Feast, Nettlefish can be found in the Sholazar Basin. If you go right to the middle of the zone (River's Heart) there are spawn pools there that you can safely fish at level 70. Just make sure you don't get too close to the threshers in the water. Glacial Salmon can be found in the Crystalsong Forest. There are other locations as well, but if you port down from Dalaran and stay near the river, it's not too hard to dodge the wolves as a level 70 and get the salmon. Deep Sea Monsterbelly are in the Frozen Sea, which you can reach if you swim WAY out from the Borean Tundra. The little chain of islands along the southeast border is what you want to aim for. Rockfin Grouper is pretty much everywhere, it's like Barbed Gill Trout.
Finally, for those of you who aren't planning to do the Coins in the Fountain Fishing achievements, I'd just like to share a few images with you: