Everything you need to know about fishing is here:
http://lisaarndt.com/phpBB2/index.php
I used to be just a small forum where a few of us NA players with Lu Shang's came to chat, now it's grown into a monster, i'm like user 21 of 577. lol
To answer your question, I started the quest at L38ish fishing. By the time i caught 10,000 moat carp i was at L50 fishing, gained skill just from a few other fish that bite while fishing moats.
I fished in 2 places.
Rabao : Carbon + Insect Paste
Windurst : Composite + Insect Paste
Rabao was the best, but it had its off days, so I went to Windurst then. I was just in Rabao yesterday while lvling sub-job though, millions of fishers, so dont' know how good it is now.