Either a prophet of the Bructeri tribe among the Germans encountered by the Romans, or, possibly, a class of holy women. May be related to the Völva or valkyrie of Norse legend.

Mention of Veleda in Tacitus:

In history we find, that some armies already yielding and ready to fly, have been by the women restored, through their inflexible importunity and entreaty, presenting their breasts, and showing their impending captivity; an evil to the Germans then by far most dreadful when it befalls their women.
So that the spirit of such cities as amongst their hostages are enjoined to send their damsels of quality, is always engaged more effectually than that of others.
They even believe them endowed with something celestial and the spirit of prophecy.
Neither do they disdain to consult them, nor neglect the responses which they return. In the reign of the deified Vespasian, we have seen Veleda for a long time, and by many nations, esteemed and adored as a divinity.
In times past they likewise worshipped Aurinia and several more, from no complaisance or effort of flattery, nor as Deities of their own creating.

...part of another statement...

Munius Lupercus, legate of one of the legions, was sent along with other gifts to Veleda, a maiden of the tribe of the Bructeri, who possessed extensive dominion; for by ancient usage the Germans attributed to many of their women prophetic powers and, as the superstition grew in strength, even actual divinity.
The authority of Veleda was then at its height, because she had foretold the success of the Germans and the destruction of the legions.