Artisan Fishing (to 300 skill) starts with Lumak (fishing trainer near hunter's guild) in Orgrimmar, who will send you to do Nat Pagle's quest in Dustwallow Marsh. Nat can be found on an island near the mainland and SW of Theramore Isle. The quest requires level 40 and 225 fishing skill, iirc.