You might be able to get all of this done with the Duemilanove; in fact, I would start with it, and the rest of the components, mainly because most people use it over the Mega, there is a ton of code out there already (and a lot of people have done GPS interfaces; plenty of threads on these forums), and it is geared toward the newbie.
There is also another reason to try this, and that would be to, in the "final product", incorporate the LilyPad 328 into the design - you would have to figure out what to do with the GPS module and LCD, but in theory you could make a "stack" with the LilyPad 328, GPS, LCD, and your buttons, and put it inside a slick round case, and end up with something real similar to that puck (especially if you can find a small LCD; maybe a Nokia cellphone serial GLCD could work?).
But first, prototype it out with the Duemilanove, then move it to the LilyPad once you are comfortable that everything is working; pick your other components (GPS and LCD, mainly) to fit in the footprint of the LilyPad. Sparkfun has plenty of options, there; if I was doing this I would go for these parts:
Arduino Duemilanove:
LilyPad:
FTDI breakout for LilyPad:
GPS Module:
MicroSD breakout:
LCD:
Plus your sundry buttons and such.
When you get to the LilyPad final, you will also want these, likely:
LilyPad LiPower Board:
LiPoly Battery:
Plus whatever case you want to put it in...
The only part that you may want to put more research into would probably be the GPS unit; I picked one of the small ones (I think it is smaller than the LilyPad) - but I don't know the particular merits/downsides to each GPS module; it may or may not be best for your application.
Hope this helps in some manner...
[edit]Another note: Some of these parts are 3.3V, some are 5V; you may need level shifters and such to get things working - which could make the "compact" bit more difficult; I am not sure how you could get around this (without having to create your own custom PCB layout)...[/edit]