Not a step-mom, but I have been a step-child, and my mom has been a step-mom. They way we worked it when my dad went into the navy was thus-My mom talked to my dad before he left, being she was uncertain if the information got properlly relayed to my step-monster (who at the time was pretty decent), she called her and let her know that I still wanted to sped time with her, my step-sis, and my little brother. I didn't go over as often as I would've had my dad been there, but I still had one overnight and one daytrip a month-minimum. Everyone was happy that everyone was accepted as family.
When my step-dads ex moved out of state for work, she took her kids for a month over the summer, and her partner had dinner with the kids roughly three times a month, and generally one weekend a month. It worked the sameway. Step-dad called ex, spoke with her, called exes partner, spoke with her, and plans were happily made.
Step-dad said he was leary to call exes partner at first, because the kids were not "her responsibility" exes partner basically told him that the kids were her family now, by choice, so there! The same basic thing My step-mom said to mom. None of the biological parents involved wanted to make plans for, or burden the step-parents, when the step-parents were just happy that they were loved and thought of as family.