Well, it depends.
If the change is not readily apparent (I'm thinking mainly Ravenloft here) go with railsdog's answer: start describing the little differences as soon as the characters notice them. Just the same you would do when they enter a tainted area of a wood, describe how the flora changed, the crooked trees, the spooky mist, the feelings of unease. The new place is not immediately recognizable as another plane, so not presenting immediate evidence is ok.
They start noticing as they go.
If the players are summoned elsewhere or travel through a portal, and this somewhere else is really different, do tell them right now. Pause them and describe the weird things now. Eberron? There's a friggin train with rails and all, and the city is totally different from the one you were before.
I've had a few experiences of the first type as a player, and several of the second kind while playing Planescape (or, as a DM, when playing Expedition to the Demonweb Pits...
...where a one-way portal to the marketplace of Sigil, with demons and angels quietly discussing while they walk and many other oddities, is found in a cave).