Here's what Take Our Word for It has to say: And to grub is simply "to dig superficially". It is thought that it was grybban in Old English, coming from Old Teutonic grub- "to dig". Interestingly, the Old Teutonic root is also the source of the English noun grave.
There is a hand-held garden implement called a grubbing hoe. I agree with Rhuby, though; I think it's just a transference from where food comes from, to the food itself. There is an expression: rustle up some grub. This implies not a planned menu, but rather "digging" through the food supply and making something from whatever is available.