We just put up a quick tutorial on how to interface the LEGO MINDSTORMS NXT and the Arduino.
This example gets the Arduino and the NXT sending information back and forth. The beauty of the examples: they can be extended to use the Arduino as a sensor for the NXT, and to develop your own sensors for the LEGO MINDSTORMS NXT system.
We have two sets of software examples from both the LEGO MINDSTORMS side and the Arduino side. We also have some schematics and pictures to help with the hardware interface.