The primary methods of detecting IMSI-Catchers and Fake BTS's is described here (pdf), and due to the variety of manufacturers' baseband interfaces, there wasn't an easy way to uniformly detect these devices.
IMSI-Catcher doesn't seem to work on my old, non-GSM Android, but I've also found OsmocomBB to be interesting; it's an open source GSM broadband implementation that seems to work on some older, cheap phones, like some motorola candy bars; check out Catcher Catcher for more info.
In terms of the IMSI Catcher devices themselves, I've seen estimations of $20 to $1500 to make one, from using cheap RTL-SDR devices to a full SDR (~$400-1500) to run a full fake GSM BTS.
The legal usage of IMSI-Catchers doesn't seem clear to me. It is essentially a MiTM attack, which at least android devices seem to go out of their way to ignore. The law enforcement usage seems worded in ways that would just confuse 50+ year old judges. And they have to go far out of the way to make sure that you don't notice an interruption in service, by forwarding any on-going communications to their intended recipients and tunneling them back, if they go are run over time and don't disassociate.
I haven't seen any estimation on how often these things are used. Besides, hacked femtocell's are probably also responsible for a lot of these rogue BTS's; I wonder if that would be discovered with such detection methods?