Gehman, dessen Vater Harold Webster Gehman ebenfalls Offizier der US Navy war[1], begann nach dem Schulbesuch ein Studium im Fach Industrial Engineering an der Pennsylvania State University, welches er 1965 mit einem Bachelor of Science (B.Sc. Industrial Engineering) abschloss. Im Anschluss absolvierte er eine Offiziersausbildung im Rahmen des Naval Reserve Officer Training Corps-Programms und trat danach in die US Navy ein. Während des Vietnamkrieges diente er als Leutnant beim I. Korps (I Corps) und war danach Verantwortlicher Offizier des als Patrouillenboot eingesetzten Schnellbootes(Patrol Craft Fast/Swift Boat) PCF 27 sowie später Verantwortlicher Offizier einer selbständigen Einheit von sechs PCF. Neben weiteren Verwendungen war er als Korvettenkapitän zwischen dem 28. Mai 1976 und dem 15. Juni 1978 Kommandant des Bergungs- und Rettungsschiffes USS Conserver[2] sowie als Fregattenkapitän vom 11. November 1981 bis zum 13. September 1983 Kommandant des LenkwaffenzerstörersUSS Dahlgren.[3] Er war ferner Offizier im Stab einer Flugzeugträgergruppe sowie in verschiedenen weiteren Stäben.
Gehman wurde im September 1996 zum Admiral befördert und löste Admiral Jay L. Johnson als Vize-Chef des Stabes der Marine (Vice Chief of Naval Operations) und bekleidete diesen Posten bis September 1997. In dieser Verwendung war er verantwortlich für die Aufstellung des 70 Milliarden US-Dollar umfassenden Marinehaushalts, der die Grundlagen für die Entwicklung und Umsetzung der Verwaltung von 375.000 Marineangehörigen umfasste. Im September 1997 bis 1999 in Personalunion Oberster Befehlshaber der Alliierten Streitkräfte der NATO im Atlantikraum SACLANT (Supreme Allied Commander Atlantic) und als Nachfolger von General John J. Sheehan Kommandeur der US-Atlantikkommandos USLANTCOM (US Atlantic Command). Am 7. Oktober 1999 wurde erster Befehlshaber des neu geschaffenen Gemeinsamen US-Streitkräftekommandos USJFCOM (United States Joint Forces Command), das aus dem US-Atlantikkommando hervorgegangen war. Diesen Posten bekleidete er bis zu seinem Ausscheiden aus dem aktiven Militärdienst am 5. September 2000, woraufhin General William F. Kernan seine Nachfolge antrat. Für seine langjährigen Verdienste wurde er unter anderem mit der Defense Distinguished Service Medal sowie vier Mal mit dem Legion of Merit ausgezeichnet.