Nat Pagle, Angler Extreme
The first and most well known refernce to Nat knowing about the sword is this item : Nat Pagle's Guide to Extreme Anglin This item is dropped at random from enemy players in the Alterac Valley Battleground. The item itself is useless, bringing it to Nat himself or to Prince Tortheldrin has no effect. The text of the item reads as this: "... and so that's where you'll find the legendary sword of the Scarlet Highlord, Ashbringer. Ain't it amazin' what you run into in an ordinary day of fishin'? "
Note that the page does NOT say that Nat actually found the sword, it only indicates that he knows where it can be found. Some speculate that he learned of it from Prince Tortheldrin in Dire Maul while fishing there. Since Nat probably has some pretty interesting stories to tell, he most likely told the Prince something interesting, and the Prince told him the fate of the Ashbringer.
There is another copy of Nat's book that you can find in Dire Maul : A Thoroughly Read Copy of "Nat Pagle's Extreme' Anglin. Now this item is unreadable unfortunatly. Right clicking on it does nothing, plus it is a grey item. As a rule, grey items are useless, and are not used in any crafting or any quest. However there are grey items that can be useful. Ancient Tablet drops in Zul'Farrak and describes how to create the hammer to summon the optional boss in that zone. So the tablet itself is not used by any quest or crafting recipie, but it's still useful to us!
Other than those 2 items, there is no concrete evidence linking Nat to the Ashbringer. There has been an enorumous amount of speculation and theory around this character in particular. This is most likely due to the appeal of the theory that a legendary-calibur weapon could possibly be attained by non-standard means (fishing), as opposed to having to delve deep into the bowls of a 40 man raid instance.
Other "fishing" rumors/theories involve the hidden pool behind Ravenholt, the "rusty flask", and the "blurry note". None of these theories have panned out, and so we won't go into details here. Any rumors that you have heard involving those items are hoaxes, despite the fact that there are usually some doctored screenshots to go with them.