What can I do to programmatically add to contextual menus? Is something similar to AddMenuCommands available?

There's an option ContextMenu, which you seem to be able to set at cell, notebook, or even box level. They all default to something like
FEPrivateFrontEndResource["ContextMenus", "something"]

That info seems to be in the ContextMenus.tr file in the \$InstallationDirectory, SystemFiles, FrontEnd, TextResources.
In any case, all that that option needs is a list of MenuItem[...]. You can look at that file (or at MenuSetup.tr) to get a hang on the syntax. Then it's just setting the option.
• You're right...you can't append menu items. But you missed a second source of context menus...the ComponentwiseContextMenu option. ContextMenu is used where you can easily dictate context menus by style, whereas ComponentwiseContextMenu` allows you to determine context menus which belong to certain box types, the various cell-related widgets, etc., which may be difficult or impossible to apply styles to. – John Fultz Mar 6 '12 at 15:52