I had the same question. The only place I've found it so far is embedded in the old Sidebar Widgets plugin from 2007 (now obsolete since sidebar widgets are part of the WordPress core):
One problem with using it as a model is that I don't know whether the old Sidebar Widgets plugin had identical coding requirements as the widgets feature now built into WP.
I wish the Codex people would make sure that the Google Search widget is up to date in a known place, and then link to it wherever it is mentioned in the Codex.
I may have been looking at an obsolete widget tutorial; this one does include a link to the old Google Search widget (which is as I thought embedded in the old Sidebar Widgets plugin). More importantly, though, it addresses changes in WP 2.8 and includes its own sample widget:
Maybe the real problem in the Codex is redundant old tutorials that don't keep up with developments in WP...