I need to add an extra template to ItemStyle.xsl using a feature deployment - any idea how to add things to that file programmatically?
Actually it might be easier (also best practice - to avoid overrides by CU, Service Packs, etc.) to have a copy of that file with your own style already in, and provision it via a Module as part of your feature!
CQWP is using multiple XSL files (3 actually) stored in the Style Library at the site collection level. You can of course chose to deploy your own in the same location (by creating a folder) and use a Module (I am assuming here the use of Visual Studio 2010 to create a solution package) or by simply copying such files manually (SPD 2010 is also a good option).
As a last step is to Export your already configured CQWP and replace the page in the XML to point to the new location (using site collection relative URLs - without host name address, etc.). Once change is performed you would to simply use "Import Web Part" in the page where needed and go from there, but this time the Web part actually points to your own. Now you only need to update the file (via SharePoint Designer 2010 directly) and refreshing should read your latest change instantly.
As a word of caution: if not changes are observed in your CQWP it means something is wrong and actually SharePoint will default to original settings, therefore your CQWP will not show other styles and it will use Default ones.