In a new game (all new characters), I feel that the players should step up and decide how they know each other. If the DM has a cool idea, that's fine, but the players should work out the details. The DM has enough on his/her plate and details like this should be fun for players to create.
As a player, I often pick another player to be my "buddy." I don't do this to form a clique (I change my buddy player every new game), but so that my character starts off knowing at least one other character very well. They might be old school chums, cousins, whatever. After I ask the player's permission to do this, I try to make the relationship flattering to the other player, such as his character saved my character's life or tutored them through school. That way, the other player is less likely to feel like the background/relationship is forced on them and it makes their character look good (and hey, isn't that what everyone wants?). DMs love it because it takes some pressure off of them and gives them background to work with.
Introducing new characters into an existing group can be tricky, but my only advice is that it should be done as quickly as possible. Nothing is worse than waiting through most of the session to have one's character introduced. The toughest part is trying to introduce a new character during the middle of ab adventure, especially when it's a dungeon crawl. I haven't tried these, but here are some ideas that might be helpful:
- The new character is being attacked by an overwhelming force. The character was with another party and all the other members have been killed. The new character may have a different goal than the party or the same goal. He or she may have an ability, a map, another clue or an item that will be helpful to the party to achieve their goal and thus make them more likely to accept the new character into the party.
- The new character saw the party several days ago and has been following them. Maybe the new character has heard of the party's exploits and wants to take part in their adventures. Maybe the new character is a messenger bearing a warning for the party. Maybe the character was sent by a priest or seer friendly to the party; the seer had a vision or was scrying on the party and sent the new character to help out.
- The new character has been living in the dungeon. Perhaps he is the last survivor of a village that used to exist in the dungeon or took a vow to live alone until he saw a sign from his god or is on some kind of quest that he has been unable to complete until the party showed up. Maybe the character was polymorphed into an animal form (such as a rat) and must try to communicate with the party.
- The new character is a turncoat. The character used to follow or was under the spell of the Boss Monster, but discovered his evil plot or the spell was broken in some way. If he can convice the party to trust him, he may have valuable information about part of the dungeon.