Map legends are important in thematic mapping, but KML/Google Earth has no build-in legend support (except the list view of map elements). I think the best workaround is to add a legend using the KML ScreenOverlay element. Unfortunately, this element only supports image overlays and not HTML layers. This makes it harder to create a dynamic legend that changes with your data.
Still, there are options: GD is an open source graphics library for dynamic creation of images. Using this library you can build a legend by adding colour scales and text to an image canvas. GD is written in C with bindings available for various languages.
The legend and map title shown in this screenshot are created using PHP-GD image functions, stored in a KMZ archive as PNG images, and added as screen overlays. You can download the KMZ file here.