Ok, finally got some leads in the docs and Google. There are actually two places this can be done, as an NSMenuExtras or as a NSStatusItem.
The problem is that apparently NSMenuExtras is a closed API, and NSStatusItem is not guaranteed to be there, as long menu items can overwrite status items if they need space.
There are some workarounds, although I am not clear how they fully work, but they seem to be more like hacks than legit code.
Anyone have any sample code that puts a Status Item up with no menu or window? I am trying to do something similar to QuickSilver (in layout, not functionality) where there is an icon on the right of the menu bar that does something when you click it.