The Paladin's mount in Pathfinder is treated as if it were a Druid's Animal Companion where the Paladin's level is used as Druid level for determining stats, etc. As I understand it, the mount is a normal beast that is raised to higher Intelligence by Divine Power and not an extraplanar creature.
The ability to call the mount to your side notably does not use the word summon but instead uses the phrase magically call and, as it is not an extraplanar creature, it therefore cannot be banished.
So, as to where the mount is before you call it: Wherever you left it. The mount is being called to your side from wherever it currently is, and where it is depends on the last place you saw it. Did you leave it outside the dungeon? Tie it up in the stables in town? Send it on an epic quest to retrieve The Holy Grail? That is the location the mount is being called from.