Is it possible to connect the lilypad xbee to an arduino uno?
Sure. Connect up Rx, Tx, Gnd, and provide a 3.3V source, I think the Uno regulator may be good for enough current.
what completes the xbee setup? is it something connected to the pc via usb?
Probably. I've read they XBees won't work without some setup, even tho Digi may say otherwise.
yes i'd reckon it's similar to the ethernet shield, involving setting your MAC address and the like in your sketch.