I would agree with lefty that you should really start smaller, 8x8x8 is a lot, really a lot. You will have to complete many stages of the project before you understand why not do do something a specific way, but by then you will have used up 500 leds, and have a huge mess.
I would suggest starting with a 3x3x3, you can probably build one and get it working within a day, it will only waste 27 leds, you wont really need other hardware (should also use 9 resistors), so you can focus on learning how to build a cube, which itself is fairly difficult.
I would then progress to controlling the cube with serial data instead of parallel data. This will mean using shift registers or LED driver. I did an instructable about converting parallel to serial with shift registers, it might be useful http://www.instructables.com/id/4x4x4-LED-cube-upgrade-with-Shift-Registers-74hc5/
You may want to charlieplex your cube, this will probably reduce the number of pins to where you can control it with a mega. By my calculations you will need a minimum of 24 pins to control 512 LEDs using charlieplexing. Charlieplexing is a bit difficult because it requires that some LEDs face one way, while others need to face another way, so building is a little more difficult. It also takes advantage of tri-state micro-controllers, so programming is a bit more difficult too.
Besides Persistance of Vision, and Multiplexing, you also need to think about duty cycle. If you have a 4x4x4 cube, you will have a 25% duty cycle (no LEDs will be on longer than 1/4 of the time), with an 8x8x8 you usually have a 12.5% duty cycle which may make things dramatically dimmer than you think. If you split your planes into 2 planes of 32 LED, then you will have a 6.25% duty cycle, pretty low! That may not work out too well, it would be best to test that before building 500 LED cube.
The other real problem with spliting the plane is that each plane creates dimensional stability, if you split the plane, you are splitting the cube into 2 rectangles that may not be as dimensionally stable.
There are many ways to skin that cat, and I've just mentioned the more common ways that I have seen.