Counter-detected in the P3-C
 

Playing the standard campaign, mission 1 with the Orion. A couple of minutes in I get a counter-detected message. It's a non-critical objective, so I can continue and complete the mission, but I was just wondering how you can remain undected when flying a plane? Especially when half the ships are destroyers with radar?

It is impossible to stay undetected with the P-3 in the first campaign mission.
Using your radar shortens the process of your detection.

In that mission, yes it is basically impossible to remain undetected. However, in other scenarios where you don't have to get as close to actively emitting vessels, you can travel at extremely low altitude and be hidden by the horizon. However, this does not work if there are AWACS or other airborne radar or recon sensors in the area. At 1,000 ft air/surface search radars are limited to between 10 and 20 nm I believe.