What I think we should do is to set a byte in the RAM that isn't used (but still saved), and each time the player warps/flies and appears in the new map, it checks to see if it is set. If it's set, which means that you still want to have them follow you, the next time the player starts moving, it makes a sprite below you, and then deals with the other (working) stuff normally. And if it's a warp-panel, you could delay the screen-fading effect a bit and stick in another "warp" animation for the character behind you.
As for surfing, you should make them jump on a "Wailmer" or seperate bike behind you. When you go onto land again, it checks to see if it's still set, and if it is, it will change the "following" sprite back to normal.
And you don't even have to do that. You could just branch an "It's not very polite when you do that..." or "He needs a POKéMON to surf." to appear whenever you try to surf or bike while someone's following you.
I would want do that, but I don't know how to even begin...