I understand that, unlike a prophage, a provirus never leaves the genome, but I don't understand how the prophage "leaves".
This is explained reasonably well at the Wikipedia entry for phage λ, which is the prototype lysogenic phage. Basically, integration occurs by site-specific recombination between the attP region on the phage genome and the attB region in the host genome. This means that in the prophage form the phage DNA is flanked by direct repeats. Excision involves the reverse process - recombination between these direct repeats. Excision is promoted by the phage-encoded Xis and Int proteins in combination with the host protein Ihf. The regulatory cascade which links cellular stress to this recombination event is detailed at the linked page.