Map styling can be applied globally via Map Locations->Settings, as well as on a per block basic.
Google Maps styles are defined via JSON format, which can be simply cut and paste into either location.
Pre-defined map styles can be found easily on the web. Popular sites are:
These sites allow you to browse pre-defined styles, offering the JSON code required. Simply copy and paste the JSON code into either the block or the settings dashboard page.
There are also online tools that allow you create new styles, http://gmaps-samples-v3.googlecode.com/svn/trunk/styledmaps/wizard/index.html?utm_medium=twitter and http://www.mapstylr.com for example offer a configuration tool.
Tip: often it is easier to pick a style that is close to your desired look and manually edited colour values to suit. JSON code is fairly easy to understand.