Making two arduinos connect

Hello
I'm having troubles with my project,at first i wanted just to use arduino lilypad,but then i couldn't figure out how to work the wireless RF transmitter and receiver with my LCD so xbee came in mind.
Now what i want to ask is,if i get xbee on lilypad and xbee on duemilanove will they be able to connect to each other(keep in mind i do not have much experience with xbee).So i'm thinking of making duemilanove handle my lcd while lilypad works on the other objectives i have.
If you need any more information i will gladly give it.

will they be able to connect to each other

The probably will, but I cannot tell you if you're able to configure that setup. First: there are different XBee modules on the market. XBee is usually used for the form factor but some use the term to identify ZigBee modules too. From the ZigBee XBees there two different series (series 1 and series 2) which are not interoperable. Usually if you buy 2 ZigBee modules (of the same series) and you power both up you can use them as if they would have wires between them (more or less). If you wanna setup a mesh network you have to change the firmware on the modules.