GPS would only be for mapping the dog's path after you get him back -- it's a receive-only device that the dog wears.
This link out of the google hit list looks to be a pretty good source of information about dog tracking collars:
http://wildlifematerials.com/dog/faq.php?q=2
The frequencies that I see being mentioned in the links in the hit list are mainly VHF and UHF frequencies, which are basically line-of-sight, and won't carry over the tops of hills. However, in the link above, they claim their system works to about 2 miles "in adverse conditions" whatever that is -- maybe raining in the woods? You might try giving their Customer Service folks a call to get more information. You might even be able to get some references of satisfied customers from them, and give them a call to talk about how well the system works.
I've noticed in many of the links that these systems are pretty pricey, though. You may need to do some shopping around to find some lower-priced systems.