It's all explained in the wiki:
Not much is known of Gibbs' early life, but it is known that Gibbs started sailing with the British Royal Navy in his younger days. 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. However, he was very lenient to pirates as he wanted to keep the rum supply he was getting from them going.
His history with Royal Navy:
Serving as a sailor of the Royal Navy, Gibbs was stationed aboard the HMS Dauntless some time later during its voyage from England to the Caribbean, carrying Weatherby Swann and his twelve year old daughter, Elizabeth, to Port Royal. Along the way, they encountered a wrecked vessel, and Gibbs voiced the opinion that it was the result of a pirate attack. Elizabeth became acquainted enough with Gibbs to recognize him on sight many years later. Ironically, while serving on the Dauntless, Gibbs was superstitious of pirates, even going as far to tell Elizabeth to stop singing a pirate song because it will supposedly invoke pirates upon them.
Some more details of how he became a pirate:
Gibbs remained with the Royal Navy for a while, though at some point over the next eight years, Gibbs turned to piracy once more. How he left the Navy is unknown, though it could have been either Gibbs deserted his post or that it was Jack Sparrow who persuaded Gibbs to turn pirate. By this point, Gibbs had known Jack well enough to be able to relate much of the man's life story and misadventures prior to his going after the treasure of the Isla de Muerta aboard the Black Pearl. He also became aware of the curse that afflicted those who removed the Aztec gold, and was aware of Sparrow's attempts to retake the Pearl following a mutiny led by Hector Barbossa.
Following Barbossa's mutiny, Jack wound up on Port Royal, where he met a local beggar named Sightless Sam who offered to join Jack's crew as a boatswain. Little did Jack know that Gibbs, who had recently deserted the Royal Navy, was Sam's assistant. By this time, they began a close friendship.