If you want also graduated color in legend, QGIS recommends you set graduation style on color and data-defined size. This works well on map canvas, but I dont get it work in composer legend.

So my solution is, first for size graduated symbol you have to use Graduated style in layer properties. As a Method choose Size. This will give you size graduation of one color.

Than you have to set colors manually double click on individual categories.
Note:
Maybe Data defined override will works for you. Try also set data defined override to changing fill of symbol with expression (in Style window click on Change..., select Simple marker and set data define override on Fill). You can use for example color_rgb()
for counting color using values from fileds. But this doesn't work for me neither, maybe it's bug, because if I set random color expression for Fill it works well, but if I use fields for values it doesn't show legend properly (QGIS 2.18.3., Linux).
