Just wanted to share my current solution with you all:
After chatting with Marcus and Madeleine at LittleBirdElectronics, we have come up with the following possible solution:
1) Xbee on The lilypad,
2) USB Arduino, Ethernet Sheild and Xbee combo to transfer messages to the WWW.
This is just one of many possible solutions, but for me this seems to provide the benefits of the low power and size requirements on the lilypad end by using the xbee instead of using 802.11 directly on the lilypad.
Besides, I already had a spare Arduino and Ethernet shield going unused, and wanted an excuse to play with xbee anyway! ;-)
Thanks all for your input! It was very useful in devising a solution.