Points of interest (POIs) are, just as the name implies, a geographic point that may be of interest to you. They are typically divided into categories like dining, shopping, lodging, recreation, etc. If you are navigating to a business, you are likely to use a POI; if you are navigating to a residence, you'll probably enter an address instead.
These days, most auto GPS receivers come with anywhere from 750,000 to 6 million or more POIs. I find units with 2 million or less POIs to be extremely frustrating to use, since often, the business I am searching for is not in the database.
I really like Garmin's approach to this. All of their newer auto units come pre-loaded with City Navigator, which has nearly 6 million POIs. TomTom fudges this a little bit, citing "miliions of POIs" for their products, though my take is that they are closer to the high end of the range than the low end.
My advice? Avoid GPS receivers with low numbers of POIs.