The linked Numberphile video mentions that a black hole the size of a human head wouldn't have enough entropy to encode Graham's number. So what diameter of black hole would actually be required?
Well, you could plug Graham's number into the Bekenstein–Hawking formula[1]. The formula defines the area and there's a factor of the plank length in there, but Graham's number is so overwhelming that the the result is pretty much Graham's number in any units you want.
So vastly large that the difference between a plank volume and the observable universe is irrelevant. IIUC, even so large that the difference — how much you’d need to scale the universe up by — is itself literally indescribable as a number which can be encoded on a universe-sized black hole.