Let's see, my campaign has added characters by:
1. At a bar.. 'I couldn't help but overhear...'
2. Converting a captured enemy into an ally
3. Catching the new PC spying on the party
4. Teleportation into dire straits with the party
5. New PC was part of adventuring party which was nearly TPK'd, was rescued, but the rescuers were ambushed, at which point the PC's stepped in to save them.
6. Happens to be travelling to the same place
7. Commended to the party's cleric by one of her priests (at higher levels, substitute 'one of the god's celestials', 'vision', etc.)
If you're in a truly remote location, item 5.) seems like your best bet. Come up with a legitimate reason, perhaps even a side-quest, which explains why your new PC would be out here in the hinterlands. If they wouldn't come here alone, give them some mythical NPC companions. Encounter the new PC for the first time fighting desperately against somebody your existing party would instantly recognize as an enemy.
"The enemy of my enemy is my friend," as the saying goes.
Item 4.) offers some plausability but is cliched.
Out of Baldur's Gate, you could offer the party the 'you find a statue'... which turns out to be the new PC, turned to stone, and there's a scroll which can unlock them... Significantly out-of-time, the new PC has little to do but join the party; the question is, will they accept her?
"Vision" offers some really good explanations for why the party might accept the new PC - "The paladin had a dream last night, in which you were fighting a black dragon, and though he recognized all of the current party, there was one warrior with you he did not recognize. The dragon was winning, and several of the party had fallen, but then the strange warrior dealt it the death blow... then the dream shifted, and he saw a stone statue, and the cleric stepped forward with a scroll, and as she read the scroll, the statue turned into the strange warrior..." ... the next day, when they encounter the statue, the paladin recognizes the face of the stranger...
Was it a true vision? Is there really a black dragon the party will encounter? Maybe.. but maybe not. Perhaps the only intent of the vision was to get the party together with the stranger, or perhaps the dragon was symbolic rather than literal.