Holiday Gift Exchange

J, 57

(,.' buys for ',"1|.)(?~6){6 4$'AndyBarbCarlDidiEarlFran'

eg

   (,.' buys for ',"1|.)(?~6){6 4$'AndyBarbCarlDidiEarlFran'
Carl buys for Earl
Andy buys for Barb
Fran buys for Didi
Didi buys for Fran
Barb buys for Andy
Earl buys for Carl

Haskell, 241 189 characters

import Data.List
import Random
main=randomRIO(0,719)>>=mapM_ putStrLn.f
f n=map(\(x,y)->x++" buys for "++y).zip(l n).tail$cycle$l n
l=(permutations(words"Andy Barb Carl Didi Earl Fran")!!)

Fully random output (that still satisfies the spec).

This generates all permutations of the list of the names, picks one at random (I think this is the shortest way in Haskell to shuffle a list - if anyone has anything smaller, I'd appreciate it), and then each person then buys a present for the next person in the list.

Golfscript: 72 64 57 chars

"AndyBarbCarlDidiEarlFran"4/{;9rand}${.n+\' buys for '}%(

Tests

$ golfscript codegolf-838.gs 
Fran buys for Carl
Carl buys for Andy
Andy buys for Barb
Barb buys for Didi
Didi buys for Earl
Earl buys for Fran

$ golfscript codegolf-838.gs 
Didi buys for Earl
Earl buys for Andy
Andy buys for Barb
Barb buys for Carl
Carl buys for Fran
Fran buys for Didi

• Thanks gnibbler for "AndyBarbCarlDidiEarlFran"4/, updated and got 7 chars less
• 57 chars solution is basically by Nabb :D, and also noticed that ;9rand is more random than my 6rand*