Ok, there seems to be something these days - found via the above stackoverflow post:
Bl.ocks (pronounced “Blocks”) is a simple viewer for sharing code examples hosted on GitHub Gist. For example, if your Gist URL is:
Replace “gist.github.com” with “bl.ocks.org” in the URL to ...
In case the deletion was done recently, one can use the Events endpoint of the GitHub REST API v3.
Look for the labels object and the content name. Then you will find the event and the context where the label was deleted. You can then restore it manually or using the API.
(My own deletion was too long ago, no way to recover it)