First problem: I think the directory structure of the zip file is incorrect. It decompresses to "google-map-plugin" but that directory contains no php file, only a directory "byrd_googlemap".
Installing this automatically (add new plugin, search, install, activate) resulted in an incorrect headers error.
So I moved byrd_googlemap directly into the themes directory.
This also threw an error.
Sorry, I know I should have copied and pasted error messages.
I just got frustrated.