I have the 0.1uF capacitor attached across the output, but the datasheet's example shows a 10uF capacitor across both the input and output of the regulator. Is the issue here with my capacitor not being big enough? I'm stumped as to what is going wrong here.
please add a 47uf electrolyte (a 100uf electrolyte capacitor would be very safe) and your problems should disappear.
And the datasheet (warning: PDF)