This is the best ad that Lego could ask for Mindstorms NXT. I had absolutely no idea that it came with touch, light (color), sound, and ultrasonic sensors. I really want to buy a kit now and see what I can do with it.
You should note that the colour sensor that it comes with can't tell the yellow and white blocks apart very well. To do what this robot did you will need to get either different stickers for the rubicks cube or buy a third party color sensor.
I have a mindstorm kit to play around and I am a linux user. To be honest I still didn't have time to do anything cool with it but I'd say the best resource is still this one http://tldp.org/HOWTO/Lego/index.html