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: