Most likely you have an underground leak -- tree roots perforating the dam, or a dry year that dried the pond and caused the underground clay to irreversibly crack, or a variety of less-common causes.
I have to say, as a pond biologist I have seen a LOT of "used to hold water but now it doesn't" manmade ponds, and in the great majority of the cases where people tried to fix 'em, they turned out to be whoppin' big money pits and never DID hold water again reliably. Not to say it can't be done, but you would have to have a lot of luck and a good budget.
Personally, I'd just forget the fish and regard it as a seasonal wetland and call it a day.
If you are really determined to do *something*, I would not suggest digging. That is likely to worsen the problem, if anything. I would cut down all trees/saplings around the dam area and consider having the dam rebuilt, BY A POND CONTRACTOR not just some guy with a bulldozer and nothing better to do.
I wouldn't personally line it -- IME that size pond with a liner, even if it is covered in riprap (and this gets real expensive), is just not at all the same as a 'real' pond. It can be done, and fish can be put in it, but it will never be 'right' IMHO.
There is nothing really wrong with a nice secluded little wetland basin, though, other than you'd have to do your fishing somewhere else
Good luck,
Pat