Gothmog is mentioned precisely once in The Lord of the Rings, and we're given absolutely no clues about his race. As second-in-command to the Lord of the Nazgûl himself, he clearly had very great authority over Sauron's forces, and this has led some to suggest that Gothmog was also one of the Nazgûl. This is by no means impossible, but it is notable that Frodo and Sam, who saw the Witch-king lead his armies from Minas Morgul, only observed one Nazgûl leading the host.
Others have speculated that Gothmog might have been a Man. We know that the Lieutenant of Barad-dûr was a Man (a descendant of the Black Númenóreans), so it seems perfectly plausible that the Lieutenant of Morgul might come from the same race. What's more, the Witch-king's companions, as seen by Frodo and Sam, do seem to have been Men.
The idea of Gothmog being an Orc seems rather less likely, but even that possibility cannot be dismissed. Ultimately, there's no hard evidence about Gothmog's race.