Hi,
you can get the legend if you are using a result map service. It's not ideal, but it will give you at least some information. Currently the REST API doesn't support Legend information on the GPResultImageLayer.
I'm accessing the original MapServer service to get the legend from there.
I will demonstrate this at the Esri Dev Summit:
http://events.esri.com/bpc/2011/dev_agenda/index.cfm?fa=Session_Detail_Form&SessionId=200&ScheduleId...
I'm basically temporary adding the result of the Tool layer to the map; retrieve the legend; Store it; and remove the layer again.
You can then add this information to your newly created layers.
The downside of this solution is that the legend doesn't actual represent your newly created layer. The legend you downloaded can have more symbols then are actual used in your result (GPResultImageLayer).
I hope this make sense.