Sharon Machlis at Computerworld notes the need.
The feature had been long sought by users (like me) who didn't want to code manual workarounds for quick one-off projects (those doing more elaborate work with the tool will likely continue customizing the legend and other look-and-feel options). Until now, you could color points or polygons based on specific data characteristics but not generate a legend within the tool; any color keys needed to be created separately.
The announcement came yesterday via a post on the Fusion Tables Issue Tracker site. This issue, and only two others, have more more than 200 requests.
Here's how to use the new feature:
I'm happy to announce we have released map legends. Legends can be configured in the "Change map styles" dialog under "Automatic legend." Create legends for - marker icons using buckets - polygon fill colors using buckets or gradients Configure appearance with - title - position on the map - a link back to your table The resulting legend appears in - your map tab (click to change the map style) - embedded maps - the generated code in the Publish dialog's HTML/JavaScript section
