Locking on to a square wave signal with minimum oversampling
One partial answer to my own question is to use the Goertzel algorithm instead of a PLL. The Goertzel algorithm makes it possible to trivially determine the power of a particular frequency; it won't provide the phase, however.

The Goertzel algorithm can be implemented quite trivially using a multiplication and two additions per sample; the sampling rate need only be a minimum of twice the frequency of the signal to be detected. Determining the amplitude of the signal from the Goertzel algorithm's output requires four more multiplies and two more additions.

Since the multiplication in the main part of the Goertzel algorithm is by a constant factor of 2 * cos(2 * pi * w), where w is the number of samples per cycle, one multiplication can be eliminated entirely by sampling at 6 times the target frequency, making 2 * cos(2 * pi * 1/6) = 1.