Fishermen can be found in many low level areas to teach you Apprentice 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 two-handed 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 cursor 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.
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 gauge 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 appropriate lures if you're getting too many failures - I find, however, that one rarely need use anything more expensive than Nightcrawlers.
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 1 Gold - 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 1 Gold. 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 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 percentage (Thottbot fishing percentages are skewed by fishing without the quest), so just make sure you're in the right zone or 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 four places, Feralas is the hardest and you will want to bring lures for it.
Tools of the Trade
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 auto-loot and recast in one stroke. Try it once and you'll never go back.
Catch by fishing hole