Captain Gaines was born on 31 July 1903 at White Sulphur Spring in West Virginia, son of Joseph Holt Gaines and Mrs. Marjorie Lewis (Gentry) Gaines. He attended Bordentown Military Institute, Bordentown, New Jersey, from 1919 to 1921, during which time he was a member of the Reserve Officers Training Corps there. Entering the US Naval Academy, Annapolis, Maryland, from his native state, in 1921, he participated in Class lacrosse and soccer, was a member of the Mandolin Club and the Pep Committee, and won the Whaleboat Lysistrata Cup as a member of the Crew during his First Class Year. As a Midshipman he became an Expert Rifleman and Expert Pistol Shot. He was graduated and commissioned Ensign on 4 June 1925, and subsequently attained the rank of Captain to date from 20 July 1943.
Following graduation from the Naval Academy in June 1925, Captain Gaines had two years' sea duty, serving successively in the USS New York and the USS Sapelo. After flight training at the Naval Air Station, Pensacola, Florida, and his designation as Naval Aviator #3410 in 1928, he joined the USS Lexington for duty as Assistant Gunnery Officer. During his period of duty aboard, he assisted in winning the Schiff Trophy and Gunnery "E" Fighting Three for the Lexington.
While on duty as Flight Instructor (Combat) at the Naval Air Station, Pensacola, Florida, in 1930 to 1932, he was a member of "Top gallants," the Pensacola Aerobatic Team. Sea duty followed with consecutive service aboard the USS Saratoga, as Assistant Gunnery Officer of Fighting Squadron 1; and attached to the USS Arkansas, as Gunnery Officer of Observation Squadron 1. During that period of duty his squadrons successively won the Gunnery Trophy.
After serving a year as Operations Officer on the Staff of Commander, Patrol Squadron 5, based at Coco Sol, Canal Zone, during which period he again won a gunnery trophy, Captain Gaines was ordered to duty in connection with fitting out the USS Yorktown. He went aboard at her commissioning in June 1936, and served until May 1939 as her Hanger Control Officer. He was then ordered to the staff of Commander Aircraft, Battle Force, as Aide and Flag Lieutenant. He later served as Signal Officer, Force Personnel Officer, and Athletics and Welfare Officer, until detached in June 1940 for shore duty.
From July 1940 until March 1942, Captain Gaines served as Commanding Officer of the US Naval Reserve Air Base, Glenview, Illinois. He then joined the Carrier Replacement Group 10 as Prospective Commanding Officer, and assumed command in April of that year. For meritorious service as Commander of that Group in the Solomon Islands on 13-15 November 1942, he received a Letter of Commendation with authority to wear the Commendation Ribbon from Commander South Pacific Force. He was relieved in May 1943, and reported in June of that year to the Newport News Shipbuilding and Dry Dock Company, Newport News, Virginia, to fit out the USS Intrepid. He joined that carrier as Executive Officer when she was commissioned in August 1943, and served as such until September 1944.
For a year from October 1944, Captain Gaines had duty as Deputy Chief of the Naval Air Technical Training Center, Chicago, Illinois, with additional duty as Chief of Staff and Aide. He reported next to the Naval Air Station, Pensacola, Florida, and from October 1945 until January 1946 had instruction at the Combat Information Center, in emergency shiphandling, for subsequent duty with Training Command, Pacific.
On 22 January 1946, he was ordered to command the USS Salerno Bay (CVE 110). He remained in that command until March 1947, and on 12 May reported to Pensacola, Florida, where until October 1948 he served as Commanding Officer of Whiting Field (Naval Auxiliary Air Station), Milton, Florida, and Chief of Naval Air Basic Training. On 14 October 1948, he assumed command of the Naval Air Station, Pensacola, Florida.
In addition to the Commendation Ribbon, Captain Gaines had the American Defense Service Medal, the American Campaign Medal, the Asiatic-Pacific Campaign Medal, and the World War II Victory Medal. He also holds the Expert Rifleman's and Expert Pistol Shot Medals.
He married the former Miss Maud Carlisle Warner of New Orleans, Louisiana, and had four children.
Captain Gaines retired on 1 June 1955, and died on 3 August 1968 at the Marine Corps Air Base hospital in Beaufort, South Carolina.