Very litle documentation exists about either of these two New World explorers. What we have mostly comes via second-hand reports about Lucas Vasquez de Allyon, another relatively obscure and poorly documented New World explorer.
Francisco Gordillo was a Captain, most likely in the Spanish Navy of the early 1520s, who reported to Lucas Vasquez de Allyon.
Pedro de Quejo was simply known as a "Spanish Slaver," apparently a "hired gun" who plied the Carribean and Atlantic Ocean plundering small islands and capturing native Indians for slavery to help the Spanish in their search for gold in the Americas.
Many folks have identifed these two as being together in 1520, but this is very unlikely since the first report of De Allyon sending out Captain Gordillo is in the year 1521. But, since De Allyon arrived in Hispaniola in 1520, it is possible that the two "linked up" as early as 1520.
In 1521, De Allyon sent Captain Francisco Gordillo to explore northward from Hispaniola. Along the way, Captain Gordillo met up with Pedro de Quejo, a Spanish "slaver," and the two of them are the first known Spaniards to sail along the Georgia, South Carolina, North Carolina, and Virginia coasts. Many rivers, bays, capes, and other geographical features were named by Captain Gordillo during this exploration, which was farily well-documented with sketches and maps that served the map-makers well in the 1500s.
Lucas Vasquez de Allyon, a judge of the court on Hispaniola sent out an expedition to search the Bahamas for Indians to be sold as slaves. If that failed, the slavers were supposed to go back to the coastal area that Salazar had called the "land of giants." Vasquez de Allyon gave this task to Francisco Gordillo, who departed Hispaniola in early 1521. He sailed to the Bahamas but found no natives. Previous slave-hunters had visited these islands on numerous occasions and had captured so many people that only a handful remained.
Gordillo unexpectedly met another slave-raider, Pedro de Quejo. The two joined forces at Andros Island and sailed north and then west. After about ten days, they finally landed near the mouth of the Santee River in what is present-day South Carolina. Among the sixty (60) or more Indians kidnapped by Gordillo and Quejo from that area was a young boy whom they named "El Chicorano," or Francisco Chicora.
Francisco was a marvelous storyteller and after his arrival in Hispaniola he entertained Vasquez de Allyon and his friends with his tales. Allyon later took Francisco to Spain, where he continued his storytelling. Although Allyon had plans to return some natives to their homeland, most of them died not long after reaching Hispaniola.
In 1525, Vasquez de Allyon sent Pedro Quejo back to the area which Quejo and Gordillo had previously explored, the "Land of Chicora." Quejo explored the coast from about 30° to 40° N latitude, and managed to establish good relations with most of the natives. He took formal possession of the land and erected stone markers with the date engraved to confirm his claim. He gave the Indians seeds with instructions for planting and hoped they would grow new crops.