i found that ocean fishing is not the best way to start, even if you can catch cobalt jellyfish at low levels. you'll fail more often or skill gains will be slower, thus discouraging you. if everyone is so eager to do the dunes/qufim/kazham route for leveling up, they should also be eager to level up fishing the fastest.
cheap method = go to the NPC fish guild or item store where they sell little worms and basic fishing rods. if you buy them from the AH then I and everyone else who knows better will just be profiting off you :-)
every one of the starting towns has such a vendor.
almost every zone in windhurst has moat carp, that is my recommendation of which town to start in. particularly, in windhurst walls, the fountain/pond near the AH.
i've tried all 3 towns and i seem to have more success in windhurst even tho my skill is higher and higher each time i visit the different towns.
there are rods for big fish and small fish. start with rods for small fish since that is what crayfish and moat carp are categorized as. they'll break when you catch the occasional big fish (not often in windhurst so people say) but if you bought the poles from NPC, you're not out very much gil.
at fishing lvl 6, i was able to fish in the salt water with sabiki rig without breaking many lines.
your rate of success is based on your skill, pole, bait, and time of day, moon phase. if you're breaking a lot of lines, even tho you occasionally catch something, you're probably fishing for stuff that is too hard or something about your set up is too hard.
if you fish in windh walls to start, all these factors are lessened.