Where/how did this menu-bar application implant itself?

To uninstall iStat Menus, please choose iStat Menus > Uninstall from the menubar, then click Uninstall. This works, even if your trial period is over. I think the uninstall process from iStat Menu themselves will do a lot more then only deleting the app itself.

You can also find the uninstaller in Macintosh HD > Library > Application Support > iStat local > Uninstaller.app

Or delete:

• Library > LauchAgents > com.bjango.istatlocal.plist
• Library > LaunchDaemons > com.bjango.istatlocaldaemon.plist

So far the iStat Menu specific part. More general information:

Deleting the app alone is not enough. There are LaunchAgents, LaunchDaemons, Preferences, Applications Support folders, Cache etc which also needs to be deleted to remove an application completely.