If the layer is an ArcGISDynamicMapServiceLayer or ArcGISTiledMapServiceLayer created using ArcGIS Server 10.0 SP1 or higher the legend is generated using the REST Map Service legend resource.
If the layers are version 10 or lower the legend is created using the ArcGIS.com legend service. In order to use the ArcGIS.com legend service your map service needs to be publicly accessible and your application must be able to access ArcGIS.com.