Other answers seem a bit complex, you can just add a parameter 'label' in scatter function and that will be the legend for your plot.
import matplotlib.pyplot as plt
from numpy.random import random
colors = ['b', 'c', 'y', 'm', 'r']
lo = plt.scatter(random(10), random(10), marker='x', color=colors[0],label='Low Outlier')
ll = plt.scatter(random(10), random(10), marker='o', color=colors[0],label='LoLo')
l = plt.scatter(random(10), random(10), marker='o', color=colors[1],label='Lo')
a = plt.scatter(random(10), random(10), marker='o', color=colors[2],label='Average')
h = plt.scatter(random(10), random(10), marker='o', color=colors[3],label='Hi')
hh = plt.scatter(random(10), random(10), marker='o', color=colors[4],label='HiHi')
ho = plt.scatter(random(10), random(10), marker='x', color=colors[4],label='High Outlier')
plt.legend(loc='upper center', bbox_to_anchor=(0.5, -0.05),
fancybox=True, shadow=True, ncol=4)
plt.show()
This is your output: