Here’s Totem before I figured out how to clear the history:

Turns out, almost all of the applications in Gnome store their history in the same place, and it can be cleared by clearing the recent documents on the Gnome menu.

Just go to the Places menu and Recent Documents \ Clear Recent Documents

You’ll get a confirmation message asking if you really want to do this.

Of course we did, and now the list is gone from Totem. 

Ahh, much better. Wouldn’t want anybody to know I was watching The Simpsons, afterall.