I have an existing MyMod which is only dependent on Skyrim.esm. However, I want it to start using data from OtherMod.

To do this, when I open the Creation Kit I select MyMod as the active file, then toggle OtherMod on as a plugin file. This allows me to see the quests of both mods in the creation kit, and link the property that allows MyMod to access the OtherMod script.

However, after saving, if I restart the creation kit, I notice that MyMod doesn't have OtherMod in the list of dependencies. If I try to load MyMod.esp, the property I linked earlier will be set to NULL. So how do I tell the Creation Kit that MyMod is now supposed to list OtherMod as a dependency, and to keep it that way from now on?

Dependencies can only be .esm files, not .esp. To have the mod be a dependency to yours, you'll have to convert it into an esm file. In that case, the people that will want to use it will need that esm too. You'll have to ask the author if he allows you to redistribute his mod as an esm file alongside your esp.