Fishing
Intro
Hello: a couple small things about fishing, it's a secondary profession so it is not lvl capped. Fishing is a great skill to make some early cash and combined with cooking you have easy access to ingredients to make, for instance, boiled clams that give a spirit/stamina bonus over 15 mins. The loot is useful for early tailors and leatherworkers that haven't come across a skinner yet as well; i caught loads of leather and cloth. On a higher fishing lvl you will be able to catch locked chests that contain nice magical items but you need a Rogue or a fairly high Blacksmith to open these chests with lockpicking/skeleton keys. There is a little melee benefit as well: your fishing skill works towards your melee rating (this is not capped to your lvl) so with a high damage fishing pole (one exists for a lvl 5 - strong fishingpole) you can whack monsters a lot higher then your own lvl to gain quick exp while hitting them with almost every hit.
List of catches by fishing hole
Fishing recipes summary
Apprentice: Getting Started
Fishermen can be found in many low level areas to teach you Apprentise Fishing. Nearby there should also be a fishing vendor, who will sell you a pole (required) and some lures (recommended, at least at first). Purchase the basic pole and the lowest level lures. There should be water nearby, so go ahead and pick a spot on the shore right by the water. Now, equip your pole like a 2h weapon. Pressing 'P' will allow you to put your new 'Fishing' icon on your toolbar. Since you're currently a terrible fisher, right-click on your lure, then click on your equipped pole. Lures are limited in duration, so don't apply it until you're ready to get down to some serious fishing. Near the water's edge, pressing the fishing icon on your toolbar will cause to you cast. A timer will begin counting down, but you'll want to be watching the bobber - I put my cursur on it immediately. When you see it bob and splash, right-click ('open') on the bobber and your fish/loot will be there - unless it gets away. Take your reward and repeat.
Journeyman: Continuing Your Career
Your skill will raise quickly at first, and you'll soon outgrow your humble newbie hole. Journeymen Trainers are common as well. Be sure and purchase a "Strong" fishing pole if you haven't already, and look for a more difficult area. The difficulty and reward of different fishing areas is proportional to the level of the mobs around it - you'll also learn to gage difficulty based on the level of loot you're pulling in and the number of failed fishing attempts. For the Horde, Orgrimmar or the Ratchet docks are great places to skill up to 150. Continue to use appropiate lures if you're getting too many failures - I find, however, that one rarely need use anything more expensive than nightcrawlers.
Expert: Angling for Fun and Profit (or not, post-nerf)
Thottbot and various knowledge bases tell what trainers will teach you 'Expert' fishing - they are wrong, based on outdated info - ignore it!. Getting 'Expert' in secondary professions requires the purchase of a book, and fishing is no exception. Again, there is no level requirement, people may tell you you need level 20, but as of beta this was not the case. Old Man Hemming in Booty Bay sells an expert fishing book for 1g - he's on the south side, somewhat near the bank. On the Horde side, most people will catch the boat to Booty Bay after skilling up Journeyman in Ratchet - if you're short on cash for the book, just fish around the Bay until you have your 1g. Then don't leave, Booty Bay is one of the best fishing holes for raising expert fishing. At first you'll need to use lures to avoid too many escapees. Here you'll be pulling up crates and locked chests - these can be picked by any rogue with 90 lockpicking (perhaps less). Your skill increase will slow down, but you'll be catching more valuable items, like bolts of silk, engineering parts, and level 30+ items. Many feel that this is where the fisherman really hits his stride - in fact, one can fish very successfully in lvl 50+ zones with 225(+55) skill (strong pole + lure).
Artisan: Zen and Art of Fishing
Artisan secondary skills are obtained through quests. When you have reached 225 fishing and are at least level 40, the fishing trainer in Orgrimmar/Ironforge will tell you to find Nat Pagle, Angler Extreme, who is in Dustwallow Marsh. The "rare" fish he wants you to catch actually have a rather high % (thottbot fishing %'s are skewed by fishing without the quest), so just make sure you're in the right zone/body of water and you should have them in no time. I found that with 225(+5) skill I was letting a lot of fish go, so it doesn't hurt to have some lures for this quest. (Anecdotally, after losing about 10 fish in Feralas I used a lure and got the quest fish on the first cast.)
Tools of the Trade: Tips and Tricks
I highly recommend the Tackle Box mod available in Cosmos (I have no experience with importing the stand alone mod to gypsy, etc) which allows you to cast by right-clicking on water when your pole is equipped (including recasting when you loot the bobber). I use this with shift+right click to autoloot and recast in one stroke. Try it once and you'll never go back.
An alternative to Tackle Box, with its dependency on the Sea library and Cosmo and such, is a spin-off called FishEase. It has all the same functions (easycast by right-clicking when rod is equipped, fastcast by looting and re-casting with one click, switch macro to change from rod to standard adventuring gear, etc) and is a stand-alone mod. Works right out of the box, no worries.
If you plan to skill cooking in conjunction with fishing (why wouldn't you), I highly recommend starting fishing at a lake where you will catch a high percentage of brilliant smallfish. You can start off fishing in Orgrimmar, but it will take you forever to catch the 50+ smallfish required to get to 50 cooking for the next fishing recipe (15% catch rate - 330 to 350 catches!). FOR THE HORDE(!!) you will catch smallfish over 50% of the time in Stonebull Lake, Sen'jin Village, or Valley of Trials (for undead, nothing in Silverpine has a great %, so just use that zeppelin early). If you're already in Orgrimmar and don't want to walk far, thottbot shows that Jaggedswine Farm (outside by the zeppelin) might be a likely spot. Go to one of these spots, and you should catch enough fish to skill cooking through smallfish and mud snappers in one moderate session in about the time you'd raise your skill enough to want to move on.