Power Map was released as part of Office 2013 SP1. You can read the announcements here:
One important point to note here is that Power Map will only be available to Office 365 customers. If you have a standalone version of Excel, or have a regular (ie not Office 365) Professional Plus license, you will no longer be able to use Power Map. See:
If you have a subscription for Microsoft Office 365 ProPlus, Office 365 Midsize Business, or for the Office 365 Enterprise E3 or E4 plans, you’ll have access to Power Map as part of the self-service business intelligence tools. To determine which subscription you have, see Office 365 ProPlus and Compare All Office 365 for Business Plans.
If you have Office 2013 Professional Plus or a standalone version of Excel 2013, you’ll be able to download and use the Power Map Preview for Excel 2013 until May 30, 2014. After that date, the preview will no longer work in any non-Office 365 subscription version of Excel.
So, yet more evidence that you need an Office 365 subscription and a streamed installation of Office to get all the latest BI functionality.
UPDATE: Meagan Longoria has the details on what’s new in this release here: