I need to find out in what country given GPS coordinates are, on a device that has no Internet access (e.g. this, but without the easy on-line solution). Having no experience with GIS, I guess I'd need some kind of module that would statically store shapes of countries and match current location against them.

I'd therefore like to ask what kind of tools would be best for this, and what is the best way to obtain the country data. I'm using Python on an embedded Linux box.

There's a shape file here with all of the country borders. You can then use OGR or something like this to access the data.