I trained up fishing from the shore until I got to 60, then you have to go into deep water (14 squares from the shore) to gain, but you should gain by the shore.
At 60, get a boat and sail in a straight line, turn round, then command slow forward..
For UOA prepare the following macro :
Use item (your fishing pole)
Target relative (near your boat)
Pause 8000 (may depend on how fast your connection is)
repeat as many times as possible.
Beware of water elementals though, and from 80 skill on, also be careful of sea serpents.