Between Arduino Mega and Duemilanove, if they are the same price (which I don't think so) buy MEGA which has more ram and I/O than Duemilanove.
If you're just starting and you can't buy MEGA really cheap, get Uno which is newer. Duemilanove is being replaced by Uno.
but first find out what do you want to do with LEDs. Are some going to turn on at the same time? (so you don't need to control all of them individually). Do you want to use a shift register or you'd like to keep it simple by controlling each set of LEDs using one I/O pin?