Firstly let me put the next sentence in capitals as it's a fairly important concept to grasp.

IT DOES NOT MATTER WHERE YOU FISH, YOUR SKILL UP RATE WILL NOT CHANGE. YOUR SKILL UP RATE IS DETERMINED BY THE NUMBER OF SUCCESSFUL CATCHES, NOT BY THE AREA YOU FISH IN OR BY THE QUALITY OF FISH THAT YOU CATCH

*NEW* Skill Up Formula
You skill up by number of successful catches. The equation is approx. as follows: (current unmodified fishing level - 75) / 25 = total # of fish required to level, with a minimum of 1 fish per catch. (see below for table)
Originally posted by Noressa on the US forums

So, with that knowledge, you'll realise that you can skill up fishing from 1 to 300 by fishing the water of your faction’s city. The reason for the different locations mentioned in this guide, is for you to be able to skill up your cooking as well.

I've combined both fishing and cooking in this guide, as they compliment each other very well and if your going to skill up your fishing, you might as well skill up your cooking with all the fish you'll be catching.

N.B. it will take you a minimum of 11 hours to complete this, but more likely about 14-15.
N.B.2. Your cooking will always level faster than your fishing. You'll have to make use of lures even more when the gap between your fishing and cooking increases. Typically, by the time I've reached 300 cooking, my fishing is anywhere between 230 and 250.

Also, please be aware that this is not a fully comprehensive guide to both cooking and fishing and was never intended to be. The sole purpose of this guide is to level up your cooking and fishing in the quickest way possible. If you want a guide that covers almost everything about these two skills then please check out Draznar's excellent guides here:

Fishing - http://wow.toshimo.com/viewtopic.php?t=272
Cooking - http://wow.toshimo.com/viewtopic.php?t=273

So let's start:

Go to your fishing trainer and cook and pick up Fishing and Cooking skills.
Buy a fishing rod and a stack of shiny baubles (a lure that adds +25 to your fishing skill).
Your now ready to begin.

Best place to start is in Elwynn Forest.
Go speak to Tharynn Bouden in Goldshire and buy the recipes for Brilliant Smallfish and Longjaw Mud Snappers. Now start fishing in Crystal Lake.
You'll want to catch about 60 Brilliant Smallfish to get your cooking from 1 to 50.
Now go to Stormwind City and fish the canals for Longjaw Mud Snappers. You'll need about 50 of them to raise your cooking to 100.
Between levels 50 and 75 go learn journeyman fishing and cooking.
Now go to Southshore and speak to Lindea Rabonne and buy the recipes for Bristle Whisker Catfish and Mithril Head Trout.
Go to the river to the east of Southshore and fish for Bristle Whisker Catfish. You'll need about 80-100 of these to get your cooking to level 175.
Between levels 125 and 150 go to Shandrina by Mystral Lake in Ashenvale and buy Expert Cookbook. You'll need to go to Booty Bay and buy a book for your Fishing level. Speak to Old Man Hemming and buy the book Expert Fishing: The Bass and You.
Now go to the Lakes outside Stromgarde Keep in Arathi Highlands and fish for Mithril Head Trout. Your going to need about 60 of these to get your cooking up to level 225.

At this point you should now have level 225 fishing and level 225 cooking. If your not level 35 yet, then this is as far as you can go. If you are level 35+ then you have two quests to complete before you can continue.

First quest: Cooking
Requirements: Level 35, 225 Cooking.

Go to Gadgetzan in Tanaris and speak to Dirge Quikcleave. He is in the tavern. He'll want you to bring him 12 Giant Eggs, 10 Zesty Clam Meat and 20 Alterac Swiss. You should actually be able to buy the eggs and clam meat off of AH, but in case you can't here's where to find them. Now according to the quest Giant Eggs drop off of Rocs in Tanaris or any large bird. The best place I found for the eggs, was the Owlbeasts in The Hinterlands. Only needed to kill about 20 of these to get my 12 eggs. They are about level 43 ish, so if your not that high a level, get help or wait till you can handle them. The clam meat comes from clams, naturally! Well to save you swimming around the sea looking for clams, your better off killing turtles at Steamwheedle Port or Raventusk Village. The drop rate is quite high and you'll have your clam meat in no time. The levels are 41 ish for Steamwheedle Port and 49-50 for Raventusk Village. The Alterac Swiss is the easiest part. Go to the Inn in Goldshire, Elwynn Forest and buy them off of the Bartender. Hand them all in and you'll get your Artisan Cooking.

Second Quest: Fishing
Requirements: Level 35, 225 Fishing.

You need to go and find Nat Pagle in Dustwallow Marsh. He is standing on a small island to the West of Theramore (58,60). He'll ask you to catch four rare fishes for him. This quest is actually really easy and the only hard part is the amount of travelling involved. The fish you need to catch are:

Feralas Ahi - West from Camp Mojache. Fish the Verdantis River where the small bridge is by the Ogres, you'll soon catch one.

Sar'theris Striker - South or North or Shadowprey Village. Make sure the area comes up as Sar'theris Strand.

Savage Coast Blue Saffin - Just outside Grom'gol Base Camp. Make sure the area comes up as Savage Coast.

Misty Reed Mahi Mahi - Directly East from Stonnard. Just avoid the Murlocs.

You should catch these fish within 5 to 10 casts at each location. So it wont take long. I haven't done this quest on my Alliance character, so I'm not sure of the best order in which to do them.
Now go back to Nat and get your Artisan Fishing.
There is apparently a bug with this quest, if go away from Nat BEFORE getting your fishing level to 226, the quest can bug and you'll be stuck on 225 for good. Didn't happen to me, but I've seen a few posts from people who it's happened to.

Go to Steamwheedle port and speak to Gikkix, You'll want to buy the following two recipes: Spotted Yellowtail and Poached Sunscale Salmon.
Either fish for Spotted Yellowtails at Steamwheedle Port or go to Raventusk Village (well not to it, just a little North of it) for the slightly better drop rate. You'll need about 30 to get your cooking from 225 to 250.
Now go to Bloodvenom Falls in Felwood and fish for Sunscale Salmon. You'll need about 30 to get your cooking from 250 to 275.
No go and speak to Vivianna in The Feathermoon Stronghold and buy the recipe for Mightfish Steak. Whilst your there buy about 40 Hot Spices and 40 Soothing Spices as your going to be making the food that you will want as a level 60 (without going into instances that is). It gives a +10 stamina buff for 15mins which is always helpful.

Now go to Scalebeard's Cave in Azshara (its one of the islands to the East) and fish for Mightfish. You'll need about 30 to get your cooking from 275 to 300. You may need to bring some lures with you at this point, as your cooking will level up faster than your fishing and Azshara is a 250+ fishing zone. Once your cooking is a 300, keep fishing till you've maxed out that too. It will take 7 to 10 catches to get one skill up at this point, so take your time.

Skill Up Table

Format = Current Fishing Level - Average Number of Successful Catches Required to Gain a Skill Up

100 - 2
115 - 3
140 - 4
165 - 5
190 - 6
215 - 7
240 - 8
265 - 9
290 - 10
***********************************************************

Fishing and Cooking 300 to 375 Guide by Highlander on EU-Terenas

Ok, first things first. A quick shopping trip.
Buy lures!! +75's preferably.
Now go and buy the Master Cookbook, to give yourself master cooking level.
If your Horde, buy it from Baxter in Thrallmar (Hellfire Peninsula).
If your Alliance, buy it from Gaston in Honorhold (Hellfire Peninsula).

Now go buy Master Fishing - The Art of Angling from Juno Dufrain in Cenarion Refuge (Zangarmarsh).

Now go buy Recipe: Blackened Trout.
If your Horde, buy it from Gambarinka in Zabra'jin (Zangarmarsh).
If your Alliance, buy it from Doba in Orebor Harborage (Zangarmarsh). Whilst your here buy Recipe: Feltail Delight.

Horde can go back to Swamprat Post and buy Recipe: Feltail Delight from Zurai.

Head back to Cenarion Refuge and fish for Barbed Gill Trout and Spotted Feltail.
You only need to catch about 25 in total too get your cooking up to 320. Your fishing level will probably only be about 305 by this stage, if your lucky (it's a long, slow process and not for the easily bored).
Cook up the Trout and Feltails.

Now take a trip to see Nula the Butcher in Garadar if your Horde or Uriku in Telaar if your Alliance. Both in Nagrand. Buy Recipe: Poached Bluefish and find a nice quiet spot in Nagrand to fish for Icefin Bluefish. Your really going to need to have lures attached here, unless you spent a lot more time in Zangarmarsh fishing.
Keep fishing till you have about 40 Bluefish and then cook them to take your cooking to 350.

Ok, the next bit requires a flying mount, as the only recipe that will take you to 375 easily is Spicy Crawdads which requires Furious Crawdads. They are only found in one of three lakes in Terokkar forest. All of which can only be accessed with a flying mount.
The three lakes are:
Lake Jorune - north west of Stonebreaker Hold.
Lake Ere'Noru - south east of Allerian Stronghold.
Blackwind Lake - in the south east corner of the map, in the Skettis area.

If your Alliance, go see Innkeeper Biribi in Allerian Stronghold (Terokkar Forest) and buy Recipe: Spicy Crawdad.
Horde go see Rungor in Stonebreaker Hold (Terokkar Forest) and buy Recipe: Spicy Crawdad.

You'll need to catch about 30 Furious Crawdads to max out your cooking.

*Update* - Blizzard added recipes for Hot Buttered Trout and Fisherman's Feast. Both of which stay orange till 375. Unfortunately the main component is so far harder to fish up than Crawdads. Hopefully this will change. But if you get any Enormous Barbed Gill Trout or Huge Spotted Fetail then cook them. The recipes are taught by the barmaid in the World's End Tavern in Shattrath City.

By this point, your fishing will probably only be about level 320. But you may as well stay in Terokkar Forest and fish for Golden Darters. When cooked, these give a +44 healing and +20SPI buff, so they are great to sell to healing classes.
Or you can head back to Nagrand and fish for Figluster's Mudfish, which give a +20AGI and +20SPI buff when cooked.
Either way, to get to 375 your going to have to make about 650 successful catches. That should take a normal person about 8 hours, so you'll want to break that up into something like 30-60 minute chunks, spread out over a period of time.
Remember that it does not matter where you fish, your skill up rate will remain the same. It's all based on successful catches. So fish anywhere you want and you'll still get skill ups.