Algorithm(s) to mix audio signals without clipping
The physically "correct" way to do this is summing the samples. However when you add two arbitrary samples, the resulting value could be up to twice the maximum value. ... The naive solution here is to divide by N, where N is the number of channels being mixed.


That's not the "naive" solution, its the only solution.  That's what every analog and digital mixer does, because it's what the air does, and it's what your brain does.

Unfortunately, this appears to be a common misconception, as demonstrated by these other incorrect non-linear "mixing" (distortion) algorithms:


Mixing digital audio (the wrong way)
A quick-and-dirty audio sample mixing technique to avoid clipping (don't do this)


The "dividing by N" is called headroom; the extra room for peaks that's allocated above the RMS level of the waveform.  The amount of headroom required for a signal is determined by the signal's crest factor.  (Misunderstanding of digital signal levels and headroom is probably partially to blame for the Loudness war and Elephunk.)

In analog hardware, the headroom is maybe 20 dB.  In a hardware DSP, fixed-point is often used, with a fixed headroom; AD's SigmaDSP, for instance, has 24 dB of headroom.  In computer software, the audio processing is usually performed in 32 bit floating point, so the headroom is enormous.

Ideally, you wouldn't need to divide by N at all, you'd just sum the signals together, because your signals wouldn't be generated at 0 dBFS in the first place.  

Note that most signals are not correlated to each other, anyway, so it's uncommon for all the channels of a mixer to constructively interfere at the same moment.  Yes, mixing 10 identical, in-phase sine waves would increase the peak level by 10 times (20 dB), but mixing 10 non-coherent noise sources will only increase the peak level by 3.2 times (10 dB).  For real signals, the value will be between these extremes.

In order to get the mixed signal out of a DAC without clipping, you simply reduce the gain of the mix.  If you want to keep the RMS level of the mix high without hard clipping, you will need to apply some type of compression to limit the peaks of the waveform, but this is not part of mixing, it's a separate step.  You mix first, with plenty of headroom, and then put it through dynamic range compression later, if desired.