In both forms, the お + [verb stem] is acting like a noun. The humble form is analogous to the [verbal noun] + する construction like 勉強する and the お + [verb stem] in an honorific form is followed by に which indicates that this part is a noun. Verb stems often can be used as a noun, but that does not seem to be the case with these constructions as you cannot create the forms without お.
× 泊まりします
× 泊まりになります
So what お is doing, besides introducing politeness, is somehow enforcing that お + [verb stem] will be handled as nominal, allowing it to be used within these constructions.
As for the honorific form, one strategy often used in Japanese is to somehow remove the agentivity from the person to be honorified. For example, a way to refer to a person with honor is to use directional/locational demonstratives こちら, そちら, あちら, どちら rather than the ordinary personal pronouns 彼, 彼女. One way of honorifying the subject is to handle that subject as a place rather than a person:
天皇におかれましては、...
'At (the location of) the emperor, ...'
With the use of the verb なる 'become', the agentivity is removed; becoming something is not volitional. That is presumably the origin of this honorific form. The reason why removing agentivity counts as honorifying is probably because it frees the agent from responsibility occuring from the action.
I have no idea why the humble form is like that.
