I have been fishing going on four days now. It was a pain at first, but got easier as I went along. Here is a list of progression. Even though I only did the Horde side, I researched all the Alliance crap too. Paladins cry enough as it is, I didn't want them to feel left out. I am working on cooking skill at the same time. Cooking and fishing, as most of you know, go very well together.

Starting out: Getting your fishing skill.

Horde Fishing (1-150)

Apprentice Fishing(1-75)

Armand Cromwell: In the Undercity. Outer circle, magic quarter, northeast.
Kah Mistrunner: Thunderbluff . Middle plateau, east section.
Lumak: Orgrimmar. Valley of Honor, at the pond.

Now you are set to get to a skill level of 75. You need to buy a fishing pole. Really cheap. If you want, you can buy bobber, lures, and other stuff that will allow you to artificially raise your fishing skill. So take that brand new fishing pole and go find a pond, lake, or ocean. No, your neighbor's swimming pool won't work, redneck.

NOTE: You can't fish in all bodies of water at a low skill. You will have to work your way up to them. If you try and fish in a body of water that is too high level for you, you will get a message saying something to the effect of "Goaway, you suck at fishing. Come back when you don't suck anymore". The best way of guaging whether you can fish or not is by looking around to see what kind of mobs are in the vicinity.

So you have fished your way up in skill. Time to go get that Journeyman rank. Not sure what the minimum skill required is (not too high, like 50), but skill level of 75 is sure to work. You can't go any higher than that anyway until you talk to a trainer.

Armand Cromwell: In the Undercity. Outer circle, magic quarter, northeast.
Kah Mistrunner: Thunderbluff . Middle plateau, east section.
Lumak: Orgrimmar. Valley of Honor, at the pond.

Yes, the same people you went to for your initial skill.

Alliance Fishing (1-150)

Apprentice (1-75)

Arnold Leland: Stormwind
Astaia: Darnassus
Grimnur Stonebrand: Ironforge
Harold Riggs: Wetlands
Matthew Hooper: Redridge Mountains

You goody goodies make me sick. You get 5 trainers. Anyway, get your fishing pole in hand, grab some beer and Cheetos, and lets go fishing. If you want, you can buy bobber, lures, and other stuff that will allow you to artificially raise your fishing skill. This will get you to a skill level of 75.

NOTE: You can't fish in all bodies of water at a low skill. You will have to work your way up to them. If you try and fish in a body of water that is too high level for you, you will get a message saying something to the effect of "Goaway, you suck at fishing. Come back when you don't suck anymore". The best way of guaging whether you can fish or not is by looking around to see what kind of mobs are in the vicinity.

So, ready for Journeyman yet? No? Then why are you reading this? Get back to fishing!!

Journeyman Fishing (75-150)

Ready now? Ok great. Head back to one of the NPC's listed above. Get your Journeyman title. You can get it at a skill level lower than 75 if you wish, 50 or so. Once you have Journeyman you are set to make it to a skill level of 150.

Alliance/Horde Expert Fishing (150-225)

So you think you have reached Ahab status, eh? Think again.

Once you get high enough in skill, you need to head to Booty Bay and buy a book to get your skill cap raised from 150 to 225.

***EDIT: As stated by Ty in reply, you have to be level 20 and be willing to part with 1g to buy the book.

Go see Old Man Hemming. From him you will buy a copy of "Expert Fishing: The Bass and You". You can buy it whenever you want, but you won't be able to learn it until you have reached the appropriate skill level. It costs around 1 gold 35 silver, depending on your faction arrangement with Booty Bay.

Alliance/Horde Artisan Fishing (>225)

You mad mad slayer of fish you!!! You have managed to get up to skill level 225. Now what? Well now you need to boogy on down to Dustwallow Marsh. There you will find Nat Pagle (Tidefury Cove, on a rock in the bay, a Nat's ass SE of map dead center, HAHA I crack myself up. Nat's ass. Get it?). You must be LEVEL 40 to get the quest.

UPDATE: Nat can be found at 58,59 Tidefury Cove

Pat is going to send you on a quest. He wants you to catch some fish for him. Yes, you have to catch them. No, you can't buy them, you lazy bastard.

Nat says:
Can't say I really enjoy fishin' much. Figure I been at it for a good 20 or 30 years now. I reckon people are driven to do what they do for different reasons. Now, I'm not saying you need to fish for 30 years or catch every fish in the sea to become a master fisherman. I reckon you just need to be determined - determined enough to sit on your duff for hours at a time, doin' nothin'. I'll tell you what, catch me a few rare fish and I'll teach you a thing or two. Here's a list:
Misty Reed Mahi Mahi from the Misty Reed Strand in the Swamp of Sorrows.

A Sar'theris Striker from the Sar'theris Strand in Desolace.

Feralas Ahi from the Verdantis River of Feralas.

Savage Coast Blue Sailfin from the Savage Coast of Stranglethorn Vale.

Go get all that stuff, take it back to Nat, and POOF!!!, you are uber. Now go catch some fish.