I've heard conflicting reports on this, some people say you need to speak with the fishing trainer in Ironforge first who then sends you to see the guy on the island near Theramore.
Others say you can skip this and go straight to the island. Just to be safe, I saw the guy in Ironforge first.
As long as I was in Theramore, I went first to Desolace (caught the fish on the first cast, nearly fainted!) and then to the south to Feralas for the second fish from the river (this took about 10 minutes).
From there I went to the Swamp of Sorrows (this one took the longest, about half an hour or more - and it's a long dangerous hike for a level 40) and then to Stranglethorn (which took about 20 minutes).
Then take the fish back to the guy on the island and you're all set.