Your experience with that app doesn't tell you anything because you don't have the source code, so you don't know what it's doing. It might be poorly written or relying on detecting SSIDs of nearby WiFi networks or any number of things.
A geofence is just a shape on a map, which is a latitude x longitude grid. If a device knows A) the shape of the geofence, and B) its own location, it will accurately determine whether it's within a geofence.
Neither of those things (A or B) require an internet connection. GPS operates independently from the internet. It's a one-way transmission (satellites -> device).
It's possible to detect location more quickly or more accurately using other sources to augment GPS. These include WiFi SSIDs, as mentioned above. That still doesn't require an internet connection -- only a WiFi adapter.
