Solution
To add the New Query Action to the Toolbar change the appropriate element in:
<Windchill>/codebase/config/logicrepository/xml/explorer/productstructure/
PDMLinkExplorerMenus.xml
To add the popup menu entries to the Uses tab change the appropriate element in:
<Windchill>/codebase/config/logicrepository/xml/explorer/structureexplorer/
ExplorerMenusForUsesTab.xml