I Matthew,
Although your sites are using K2, this isn't really a K2 question, but more a Joomla question.
I would suggest to ask on the Joomla forum site instead, unless your lucky and someone here has done it.
Do they all share the same database?
You are also going to have to look on the Joomla extension directory to see if there is a cross database search extension.
I did look at an extension a couple of years back (1.5) which linked many Joomla installs across multiple databases, but I cant remember its name.
Regards,
Simon