The xt_geoip module included in Xtables-addons is the continuation of the module from Nicholas "acidfu" Bouliane (the old geoip page).
During its lifetime in Xtables-addons, xt_geoip has been changed from a linear search to a much more efficient bisection search and, as of Xtables-addons 1.33/February 2011, also supports IPv6 lookups.
Installation
A handful of distributions provide ready packages for Xtables-addons, so there is not much to say besides: check with your local package management system. The geoip database is also sometimes included (if not — contact your distro today!).
Manual install
After installation of Xtables-addons, you still need to install the database files for xt_geoip. Shipped with xtables-addons come two helper scripts, xt_geoip_dl and xt_geoip_build. When using a pre-made package, they should be located in /usr/libexec/xtables-addons (or sometimes /usr/lib/xtables-addons). If the distro package failed to provide them, they may also be found in the source tarball.
xt_geoip_dl calls wget on the (hardcoded) URLs of the DB-IP service and unpacks the retrieved files into the current directory. Then, xt_geoip_build can be used to transform that data into the packed format:
xt_geoip_build -D /usr/share/xt_geoip *.csv
The result will be put into /usr/share/xt_geoip, which is exactly where the iptables plugin will look.
There are two extra scripts, xt_geoip_dl_maxmind and xt_geoip_build_maxmind which are copies for the Maxmind service. Maxmind's database is not public anymore, so xt_geoip_dl_maxmind probably has little value by now.
Variants
The IPv6 update in Xtables-addons 1.33 changed the filenames slightly; the database files now carry extensions .iv6 and .iv4 (short for Integer Vector, since that is what those files essentially are). Be sure to use the xt_geoip_build script from xtables-addons 1.33 to generate the IV files for xt_geoip 1.33.
geoip vs ipset
xt_geoip uses the (probably) most efficient format, a (non-compressed) packed blob. Loading one country into the kernel costs as much as the file on disk.
Since ipset does not support arbitrary IPaddr–IPaddr ranges, one would need to approximate that using, for example, multiple Network/Prefixlength entries. Furthermore, if a hash set type is used, you can assume that, by the nature of hashes and/or trees, some buckets remain empty and/or additional metadata is required. The memory footprint with an ipset-based geoip thus is naturally larger. User reports[1] indicate it can become two orders of magnitude higher in certain cases (iptreemap).
xt_geoip's lookup time is O(log2(ranges)), so to lookup an address within 20,000 ranges, at most 15 iterations each with address comparisons (at most 3) are required. ipset uses Jenkins3 for hashing, which has a certain time cost of its own.
No empirical timing tests have been conducted so far.