In Pded special fishims. They vary some, depending on the zone. These pools include the new Sagefish and Greater Sagefish, as well as Firefin Snapper, Oily Blackmouth, Deviate Fish, and floating debris piles where you can get (unlocked) trunks that contain crafting materials and equipment.
Also, in Azshara, there are swirls called Patch of Elemental Water, where you can fish up various items as Globe of Water, Elemental Water, and Essence of Water. Located mostly in the Bay of Storms, these are arguably the highest level and most profitable fishing spots in the game.
First, in order to fish there, you need a ridiculous level of fishing skill. A total of 420 is needed to guarantee landing what you catch, though you can make the attempt to fish with as low as 350 (I believe) You will rarely land a fish with that skill level. Use lures and equipment to raise your skill if needed. The best fishing items can be gotten at the Stranglethorn Fishing Extravaganza contest, so you may want to try that...with the items there, you can get your skill to 350, there is a +2 enchant for gloves, and lures give up to 100 bonus as well. In my observation, if you can get your skill to 420 with some combination of the above, you won't miss many fish at all. I regularly fish at 415, and only miss a very few.
The pools that contain the elemental items are spread through the zone in the coastal area known as the Bay of Storms. The area is patrolled by mid-50 level elite giants (as well as a few other mobs), but they're mostly easily avoided if you aren't too low a level. These pools are in set locations around the bay. At least 2 pools can spawn at the same time. There are 6 locations we've discovered, and the locations are shown on the map I've made
The patches themselves look like this
Notes:
Location 1 is slightly outside the 'Bay of Storms' itself, and requires a lower fishing level
Location 2 is at Hetaera's Clutch
Location 3 is at Scalebeard's cave
I'll include more information as it comes up, and feel free to contact me if you want to contribute to the cause...I can be reached in-game (Thalenia on Uther), or drop me a note at thalen (at) earthlink.net.
I've been searching the unconfirmed spot for a couple weeks now and I've never seen it spawn. I'm fairly certain it doesn't exist. (edit: arveene - mal'ganis - alliance)
Other spawn locations have been surveyed over time (by Arveene and many others), and don't appear to be valid. Occasionally, after fishing enough of the 6 spawns, they all stop appearing for a period of time, which lead people to believe that there were others. Most likely, the spawns simply go away for a while and reappear in the known 6 locations at a later time.