Basically, you draw a fake patch with the same parameters as your fill (see example below).
def fill_between(x, y1, y2=0, ax=None, **kwargs):
"""Plot filled region between `y1` and `y2`.
This function works exactly the same as matplotlib's fill_between, except
that it also plots a proxy artist (specifically, a rectangle of 0 size)
so that it can be added it appears on a legend.
ax = ax if ax is not None else plt.gca()
ax.fill_between(x, y1, y2, **kwargs)
p = plt.Rectangle((0, 0), 0, 0, **kwargs)