Let's say I have a web service that allows users to insert a piece of JavaScript onto their page which, when loaded, will grab a widget from my server and insert it into their page. How might I go about doing that, and what techniques should I use?
document.write?
Depends on what your widget will do.
Simplest way may be by opening an iframe and loading the widget in it. Something like google does with adsense ads.
In addition to Vasil's answer, in some situations a (dynamically generated) image might be enough. In extreme cases you might even consider Flash.
A step by step article on DIY widgets - How to embed your site on another site. It reproduces the technique used by Google Adsense