Sentences don't exist in isolation. For someone to say "They are fishing" requires some context, perhaps it is the answer to a question.
Perhaps "They are fishing" does not provide enough information, in which case you may add where they are by saying "by the old bridge", "in the river", "on the pier" or "in the sea". However, "in the sea" in this sentence suggests that they are standing on dry land.
If they are fishing in a boat at sea, I cannot think of any situation where the most important thing to add to the clause "They are fishing" would be "at sea". Either it is superfluous because the other person knows they have a boat they often use for fishing, and "They are fishing" by itself means that they are out at sea in the boat. or if the other person doesn't know about the boat, then being in a boat becomes the most important thing: "They are out in a boat" or "They are out fishing in a boat".