User "fruitkid101" has a short and to-the-point video up on YouTube on how to construct a 3x3x3 LED cube, and drive it with an Arudino. What distinguishes his video from the hundreds of other LED cube videos out there, is that he explains step by step how to arrange the LEDs and route the wiring. Secondly, as it's only three layers and nine columns, he needs no other components (save for resistors and three transistors), and all twelve wires are hooked directly up to the Arudino.

Another interesting and instructive video is Kevin Darrah's on a 8x8x8 RGB cube. (Unfortunately, it wont show in HTML5 yet, but can be downloaded with the Video DownloadHelper Firefox plugin). He explains how to construct the towers which make up the cube, and also goes into detail on testing the LED and connections along the way. Much more work, of course, but also looks very cool.