<p>What is the best way to write a Safari extension? I've written a couple XUL extensions for Firefox, and now I'd like to write versions of them for Safari. Is there a way that would allow you to add buttons or forms to the browser UI, since this is not possible with an Input manager or Service menu?</p>

Safari plugin development is non-trivial. The interface is written in Objective-C, and most of it is not even part of WebKit (so you can't see the source), but there's machinery to inspect and patch the object hierarchy of a running application. It requires understanding of Cocoa and Objective-C, but no lower.
Here's a high level overview I had in my bookmarks of the process
http://livingcode.org/2006/tab-dumping-in-safari
. It goes over creating Safari plugins using Python with working (probably outdated) code. Instead of Python you can use anything that has Objective-C bindings.
There are two major parts to it:
You need to attach your code to a running Safari. This is typically done with SIMBL
http://www.culater.net/software/SIMBL/SIMBL.php
.
Once you're inside, you need to figure what to patch. There's a tutorial on reversing Cocoa applications
http://www.culater.net/wiki/moin.cgi/CocoaReverseEngineering
, which links to the most important tool, class-dump
http://www.codethecode.com/projects/class-dump/
(the link on wiki is broken). Class-dump gives you a complete hierarchy of Safari's classes, where you can guess by names what, specifically, you need to patch. This is a very trial and error mode.
Reading the links above will give you the scope of the project.