Riddle Me This, Mr Pair Programmer

"So, my programmers were pairing; one was on the middle-tier stuff, the other on the UI layer. Things didn't seem too efficient to us. What's up?"
Two people working on different "pieces" of the same story, even if simultaneously, is not "pair programming" - this is plain old fashioned delegation. In fact, this often decreases overall productivity, due to the fact (one of many) that putting the pieces together often exposes mismatching interfaces requiring varying degrees of rework.

"Pair programming" means two people working together, side by side, on the same exact piece of code - two people thinking and talking together, one person [happens to be] typing. Furthermore, 'one person typing, one person watching' is also not "pair programming"; the key to pairing is two people thinking as one...two people collaborating.

"How to best go about selection of pairs?
Pairs should typically not be assigned, they should be formed naturally on their own. [But, see the next question for more info]

"I suspect that some pairs, for example two junior programmers, might be less effective and thus decrease productivity and code quality. Is this true?"
Yes, technically there is some truth to this... at least at the beginning. Part of the point of pairing is to help share skills and knowledge, so it may help to match up more skilled with less skilled.

BUT, much more true when you start pairing as a team, not so much once you've been at it for a little while. Once everyone is of relatively equal understanding (of the practices at least) everyone should pair with everyone. The only requirement is that the two people get along from a personal POV (and if they don't, maybe they shouldn't be on the same team anyway?). Within reason, the more "movement" the better. @see Promiscuous Pairing.

Also, something else to chew on. Having "preset/preference" pairs actually works a bit against the desired outcome - the essence of PP is having "two heads" working on one problem, in sort of a checks & balances way; the longer 2 people work together, the more they become "one head", which in large part works against the goal ("two heads collaborating").

"Do we need a certain minimum level of skill across the team before taking on pair programming?"
Absolutely not. Getting to a shared higher "level of skill across the team" is an outcome of PP (not a prereq).

"Is there a way to verify the quality of a pair that is not that experienced?"
The team should simply pay attention and use common sense.

"Is PP appropriate for some tasks and not others? Aren't small complexity activities not worth pairing on, since it just delays them?"
No.

First, on a slight tangent, part of our goal as craftsman in general is to make all tasks "small complexity", ie. simple - small stories and evolutionary design exist in large part to virtually eliminate "large complexity" altogether. When everything feels like a "toy example", then we've succeeded.

Anyway, the "stupid typos"/"silly decisions"/"shortcuts"/etc are actually more likely to occur for the "simple tasks" becuase the programmer often sees it as just that: "oh, this is just a simple little thing, I don't really need to TDD/[fill in the blank], what could go wrong"...and wallah, we've got a broken window.

Now, all that said, yes, if the task is truly a few minute trivial thing, then it may not help to PP. As with all things, common sense is required.

The truth is that the time where one in fact might be better off working alone is when they have a real doozy of a problem that they need to concentrate very hard on to get their head around. If you need some quiet dorm room time, go ahead and split up for a stint. Prototype, spike, get your head about you, then regroup and get to it. Rule is though: "No non-throwaway code during solo time".

"Should teams adjust their expected velocity to account for the effect of pair programming, especially when first adopting?"
My experience is that velocity rarely decreases enough to try to predict it - assuming they pair effectively (which is not hard), the benefits are often gained immediately.

"Do we need to pair from the onset of a story?"
Yes.

"In other words, can a story be begun by one person, then a pair picked up halfway through?"
Not advised.

Pairing actually tends to be a bit counterproductive if "picked up halfway through", mostly because the "pair" comes on and is quite likely to become, at best, a bystander observing what the other has done / is doing, or, at worst, just "a pain who won't stop poking holes in my design".

Again, true pair programming means the two are largely thinking as one, just so happens only one person is typing.

If pairing is attempted "half way in", the result is often "one person thinking, another person simply watching" - which, consequently, is more of a waste of time than a benefit.