The app works by using a web service to find out information about phone numbers. If you're so inclined, you can even run your own instance of the web service - but don't worry, you don't have to.
On phones where simultaneous voice+data is not possible (CDMA phones, such as those on the Verizon network), unless your phone is also on wifi, you will not be able to get CallerID information while the phone is ringing.
Currently supported countries:
United Kingdom (only geographical info)
The application is Free Software available under the GNU GPLv3 license. The source code is available at http://www.integralblue.com/callerid-for-android/ Grab the code and submit some patches (bugfixes, features, easter egss, whatever) if you feel so inclined!
If you have a problem with the app, please leave a comment and let me know. Especially if you chose to return the app - please leave a comment as to why.