Use or Extend module functionallity
I'm not sure that you need to dive into any theming. The Google js API uses an empty div and javascript to fill it. Your could create a custom module with a block hook to create your block. It would also load the necessary js to engage the Google API. This assumes that you are going to access the geographic information for the map independently - i.e. via accessing the database or whatever on your own. I think it makes most sense to use something like Openlayers if the data is stored in nodes and you want to use a View to access it.

If you need to theme the block outside of the map, you could use a straightforward theming function, also in your custom module. Creating or using a template makes most sense if somebody else who is more of a html/css person with less php/js experience is going to be doing the theming. If the theming is simple, you could just create the needed id and class tags in your module and then theme it via a css file.