Turns out there's an easy way to quickly remove all highlights and annotations in Preview.app on OS X:
- Go to Tools > Show Inspector
- Click the Annotations button on the far right
- Click one annotation in the list and press ⌘-a to select all, then press the delete key.