Your description is not explicitly stated, it says it works with any module that has location.
"So if the Locations Map is not showing anything on a map then this means that there is nothing to show, i.e. there are no any entries on your site with a Location defined*
How do I define locations to make it work?
Correct. "it says it works with any module that has location." - exactly, i.e. a data entry must have a location set already in order to appear on a map. And also it clearly states in its description
Also you may be interested ... in Location Picker module which allows to use Location field without having to use Google Maps.
To define locations you by default you need to configure Google API to make the Location fields work on a data post/edit forms. Alternatively you can use the Location Picker module which will replace the default Location field with an interactive map.