What is a "Bitmap heap scan" in a query plan?

The best explanation comes from Tom Lane, which is the algorithm's author unless I'm mistaking. See also the wikipedia article.

In short, it's a bit like a seq scan. The difference is that, rather than visiting every disk page, a bitmap index scan ANDs and ORs applicable indexes together, and only visits the disk pages that it needs to.

This is different from an index scan, where the index is visited row by row in order -- meaning a disk page may get visited multiple times.

Re: the question in your comment... Yep, that's exactly it.

An index scan will go through rows one by one, opening disk pages again and again, as many times as necessary (some will of course stay in memory, but you get the point).

A bitmap index scan will sequentially open a short-list of disk pages, and grab every applicable row in each one (hence the so-called recheck cond you see in query plans).

Note, as an aside, how clustering/row order affects the associated costs with either method. If rows are all over the place in a random order, a bitmap index will be cheaper. (And, in fact, if they're really all over the place, a seq scan will be cheapest, since a bitmap index scan is not without some overhead.)