What would be the best way to light an outdoor interview? Shooting will probably be taking place in the early morning or evening, in shade.
Would a simple reflector be enough?

There's probably no BEST way, as it will always depend on the actual situation, and there will be several ways to do what you want. If you've ever seen news footage of LIVE on-site events, the announcer/news person is often pretty well lit, sometimes VERY well lit.
This can look quite "artificial" and not the look you are after.

The reflector would work well, providing there is light from somewhere which can be reflected!
We did a quick test last week using two of our LED lights, and were quite satisfied with the results:
http://vidled.com/test-september2005.html

(a backlight would of been nice, but the lighting may have been quite similar to what you described)