The word to spell is "EXTRA" for the free man. I like to ignore the cherries and kill the bad dudes. The more you can crush with a single rock, the greater the score. I like to get all but one or two and then go for the prize to get the letter. Make sure to get the prize when a letter you need is highlighted, it changes at random, unless the letter happens to be roaming the playfield, I try to shoot them whenever they venture out before getting the prize (that way getting 2, sometimes 3 letters per board). The prizes get extremely valuable after about level 7, so they shouldn't be ignored.
The diamond is completely random, and it's not worth losing a life chasing, the only benefit is 8000 points (unless you're actually paying a quarter to play the game).
Use your "bouncing frisbee" sparingly, it sometimes takes a long time to return to you, you're pretty vulnerable without it. After you eat the prize, though, it returns to you pretty much immediately until normal play returns (you shoot the letter), so if you want to kill the bad dudes that escort the letter for some extra points, that's ok. Just remember that once the letter is killed, the frozen monsters will return to life right away, so consider your position relative to them when deciding when to kill the letter.
Me and a couple of my friends have been competing on this game for a while now, by our standards (we're not awesome, but we're good for about 270K or so) a good game is one where you average 10K or more per level. Most of my strategy involves pushing an apple out slightly into a vertical tunnel and waiting for the monsters to accumulate there. You can do this until one of them starts changing colors (indicating he's about to start burrowing straight at you) and then get them all. 6 or so on a single drop is awesome. The prizes are very valuable after about level 8 or 9, progressively so thereafter, so it's a good habit to get into of getting them before killing the last dude, even if you're not trying for an extra man.
If you find yourself without your bouncing frisbee and a monster hot on your tail, move in straight lines as much as possible, they will as often as not stop for a rest before coming back at you, giving you a chance. If you turn you lose a little bit of ground versus going in a straight line (doesn't matter if you're "digging" or just running through a tunnel).
Mr Do is awesome!! I never played it back in the day, hated it actually, thought it was a sloppy Dig-Dug ripoff... Discovered it on MAME, definitely one of my top 10 all-time favorites.