Gibbs was a pirate sympathizer during his naval career and was friends with both Jack and Edward Teague prior to the events depicted in The Curse of the Black Pearl
At some point in Jack Sparrow's teenage years, Jack and his father Edward Teague were captured by the Royal Navy. Gibbs, being friends with Teague, secretly helped them to escape their cells, being able to do this only because he was a sailor in the Royal Navy.
—Jack Sparrow: Sins of the Father (via PotC Wiki)
At this time, I do not believe there is a canonical answer as to Gibbs' descent from the Royal Navy to a pirate.
There are a few theories I have heard/derived:
The series implies that Jack Sparrow's initial voyage to Isla Muerta may have been a catalyst to Gibbs' descent. It may have also been a separate adventure of Jack Sparrow's, most likely, after rechristening the Wicked Wench to the Black Pearl.
I recently saw the first film again and Gibbs actually tells William Turner that he did not know Jack until after he had lost the Pearl. This seems to be a continuity error among the various media sources for PotC.
Another less exciting theory is that Gibbs followed a common career path to piracy which was a privateer. Privateers were contracted sailors† who committed acts of piracy under a writ from a given nation. It was not uncommon for privateers to be retired Naval officers/crew as they were some of the best sailors and knew how their targets operated. It was not uncommon for privateers to become pirates by operating outside of their writs. Some of the most famous pirates were believed to have started their pirate careers this way‡.
† Generally the privateer writs/contracts were not given to sailors; rather, the officer or commander of the vessel was issued the writs/contracts.
‡ Many historical pirates' early lives are shrouded in mystery due to poor record keeping and the fact that many pirates changed their name and backstory.
A bit more exciting and not an uncommon occurrence was that while on a Naval expedition, Gibbs' crew mutinied and resorted to piracy as a way to escape court martial. I find this not too far fetched as Gibbs already showed he was sympathetic towards pirates. Being a warrant officer in the Royal Navy, he may have commanded more respect from the crew than the officers; enough to stage a mutiny.