The easy part is connecting the GPS, there is some information on connecting a GPS in the [u]Arduino playground[/u] , this one is a good place to start: Arduino Playground - GPS
The challenge will packaging the complete system to be small and robust with a suitable power source, a practical means to get the data out, and an antenna layout that has sufficient visibility to GPS satellite data when attached to wildlife.
You may want to start a new thread where you can say a little more about your requirements and encourage contributions on various solutions. I would definitely think its worthwhile pursuing further.