This is possible due to the simple two-to-one relationship between the frequencies of musical notes which are separated by an octave.
Octave-down effects are typically produced by converting the signal to a square wave, and then using flip-flop circuits to divide the frequency by two.
Jimmy Page used a Blue Box to record the solo on Led Zeppelin's Fool in the Rain.
The Boss OC-3 (2006) has an additional mode called "Poly" where only a low note is added with the idea to add a bass line to chords.
The song Seven Nation Army by The White Stripes features an octave pedal on electric guitar, simulating the sound of a bass.