How to add a Safari toolbar button that runs an AppleScript

How do I add a button to the Safari toolbar that, when clicked, executes a given AppleScript?

I don't think it can be done unfortunately. To put a button on the toolbar, you need to write a Safari Extension, which are restricted in what they can do. They can't execute any sort of arbitrary code outside of Safari. You can read more on developer.apple.com.

Another solution, and this is really dependant on what you want to do, is to use Services to execute your Applescript.

It doesn't create a toolbar icon, but will allow you to create a service from your AppleScript. You can then define a shortcut key in the System Preferences Keyboard Services pane

This page over at automatedworkflows.com shows an example as well as a link to the rather useful ThisService program.