Fishing
Fishing is one of the secondary WoW Tradeskills, and is a great skill to get ingredients to use your Cooking skill for some food to heal between fights at a low level.
Intro
Most of the items that you recieve from fishing will, of course, be fish. But there is a small chance that you can find other items such as boxes (will most likely need the help of a rogue to open them), potions, or even a green item.
Most parts of the world have a minimum fishing skill requirement which generally scales along with the level of the creatures in that zone, although some places can not be fished even with a skill of 300. In order to improve your fishing skill, all you need to do is fish. It doesn't matter where you fish, as long as you catch something your skill will improve. At lower levels, you will usually gain one point for every fish you catch, but at the higher levels it will be more like one point for every 10 fish. While you can skill just as easily in a lower level zone as a high level zone, the higher the level of the zone the better the fish (and loot) you can get.
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, just about any trainer that will teach apprentice fishing will teach Journeyman. 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)
Getting 'Expert' in secondary professions requires the purchase of a book, and fishing is no exception. There is no level requirement for purchasing the book, however you need to be level 20 in order to read the book and progress in fishing beyond 150. 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).
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. You will need to fish in the follow places: Desolace, Swamp of Sorrows, Stranglethorn Vale, and Feralas. Out of those 4 places, Feralas is the hardest and you will want to bring lures for it.
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.