It looks like overlayfs removes most of the tricky questions by only allowing the topmost filesystem to be read-write. In that case rm is pretty simple: remove it from the topmost filesystem if it exists there, and make a tombstone if it exists in a lower layer.

Unionfs is significantly more complicated.