Routes 103, 105, 106, 107, 108, 109, 110, 115, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133 & 134, Dewford Town, EverGrande City, Lilycove City, Mossdeep City, Pacifidlog Town, Seafloor Cavern, Shoal Cave, Slateport City (Fish)
Unless fishing is listed afterwards, you just find it by surfing on Water's surface.