We don't know
Gandalf's very next line is (emphasis mine):
Far, far below the deepest delving of the Dwarves, the world is gnawed by nameless things. Even Sauron knows them not. They are older than he. Now I have walked there, but I will bring no report to darken the light of day.
The Two Towers Book III Chapter 5: "The White Rider"
And that's all Tolkien has to say about that.
In his blog, noted Tolkien fan Michael Martinez engages in a little speculation on the subject, but there's not a lot he can say; he suggests three possible explanations:
- Aboriginal spirits (that is, spirits created by Ilúvatar to inhabit Arda extremely early in its creation) like Tom Bombadil
- Úmaiar, evil spirits aligned with Morgoth who later went wild
- Creatures created by Morgoth before Sauron's rebellion
I'm going to quote Martinez briefly, because he concisely states the only thing we can say definitively about them:
To say that they are older than Sauron implies that they existed in Middle-earth (Arda) before Sauron arrived.
"Valaquenta" seems to imply that the Maiar did not join the Valar until after the Valar began shaping Arda; Manwë called upon them to help drive Melkor off into other regions of the universe. But Arda was at this time still in a very fiery state. It seems unlikely to me there was anything living there. Tom Bombadil and other "aborigines" of Arda must have been created by Ilúvatar after Arda had cooled and become a habitable place. This would explain why Bombadil thought of Melkor as coming "from the outside".
"What Are the Nameless Things?" Middle-earth & J.R.R. Tolkien Blog by Michael Martinez
But we don't know anything definitively.