I've been toying with making something similar but have purchased a GPS module
that apparently has built in logging capability. My plan is to attach it to the Arduino to load the sketch and start the internal logging. Then while applying power to the module (single cell Li-Po battery) attach it to my riding jacket, for example, take a ride and when I return extract the captured data. I just picked up a couple 750mAh li-po batteries and the module appears to at least lock with just the battery connected.
I also picked up this GPS module
in a different form factor. Since I'm still learning about both the Arduino and GPS stuff it's been a pretty rough start.
Zozie, are you providing the sketch you are using or are you anticipating making this a commercial product??