What's the recommended way to upgrade from Joomla 1.5 and multisite 1.2 to Joomla 2.5 and multisite 1.3? I tried looking for some documentation on how this was done but was unable to find it.

Upgrade multisite to 1.3 first, use SP Upgrade to upgrade joomla (cyend.com/extensions/extensions/componen...joomla-from-15-to-16) and then fix template errors?

YES you need to start by the upgrade JMS to also benefit of the Maintenance menu.

The SP upgrade extension and the JMS maintenance menu are complementary.
You can effectivelly use the SP to upgrade your Joomla 1.5 datamodel structure to a joomla 2.5 datamodel structure.
As the SP tool can not be run iterativelly, you can use the JMS maintenance menu to detect the potential errors and fix them.

As usual, perform a backup of your environment before upgrading it.
We also publish on the free download a shell script that can help you doing backup.

It is also recommended to perform the upgrade on another "test" environment (ie. a local PC/Mac) to test the upgrade before applying it on a live environment.
This will help you identifying the potential issues.

It is also recommended to update/upgrade all the extension present in joomla 1.5 before upgrading joomla 2.5. Verify that the extension that you have currently in your joomla 1.5 can run on Joomla 2.5.
Sometimes, some extension require that Joomla is upgraded to install their latest version.