O XBee não se conecta a internet, apenas possibilita uma comunicação wireless entre outros módulos, enquanto com Wifi, o Arduino se conecta à internet sem fio. =D
Com o Arduino Duemilanove e wireless, creio que só assim mesmo (XBee Shield), mas existem outras formas, mas com placas não oficiais, como por exemplo o Seeeduino Stalker, que não necessita de um Shield XBee, pois a placa já é própria pra trabalhar com xbee.
Nesse link tem o Wi-Fi Shield, para conexão Wi-fi. (Não conhecia antes)