I am wondering if this adverb is ever used or if you would restructure to "Their performance today was average." or something similar. Which adverb could I use in the above sentence?
As FumbleFingers mentions in his comment, "averagely" is a word, but it's not one people seem to use. There are many other words you can use in this context, "adequately", "unremarkably", "unexceptionally", "competently", "blandly", "tolerably", "passably" and so on. All of these are probably better used as an adjective, as in:
Their performance today was unexceptional/ acceptable/ adequate/ etc.
or before the noun:
They gave an unremarkable performance today (but still managed to beat the other team).
I think you could use okay adverbially there:
They played okay today.
According to M-W.com, okay as an adjective or adverb can mean "fairly good : not very good or very bad", which to me encompasses the "average" (especially as in "unremarkable", "normal") sense that I think you're looking for.
Another alternative would be so-so:
They played so-so today.
M-W.com defines so-so as "neither very good nor very bad : fair or average" and allows its use as an adverb. (They also provide a few synonyms, such as "middling" and "tolerably".)