The FCC sets up frequency allocations for all sorts of things like broadcast TV, AM and FM radio transmission, radio frequency door openers, cordless phones, etc. Interfering with any communication type is illegal. This is not something that is unique to cell phones.
Generally speaking, government facilities which contain classified information do not allow the operation of cell phones in the area, and are permitted to use cell phone jamming devices.
Cell phone jamming (and any other type of signal jamming for that matter) isn’t exactly rocket science. You find the frequencies the device works on and broadcast out noise on the same frequency so that the receiver can’t get any intelligable signal. Cell phones operate at fairly low power, so if you are close to where the cell phone is operating, you don’t need too strong of a signal to jam it. The farther away you are, the stronger your jamming signal needs to be.
A lot of structures make natural faraday cages. Any steel frame building forms a natural (if slightly leaky) faraday cage. There is no requirement in construction that demands that a cell phone must work in all areas inside a building.
You can make your own faraday cage very easily by just stapling metal screen to the walls. Commercial faraday cages (used to shield computer equipment, etc) are just made out of copper screen. Faraday cages aren’t rocket science either. All you need is a conductive metal box of some sort. A metal toolbox makes a natural faraday cage.
If you intentionally screened a building just to prevent cell phones from working in it, you might open yourself up to lawsuits from people who say you are preventing emergency services from being able to communicate in an emergency situation. You might want to check with a lawyer before doing something like this. Genearally speaking, though, faraday cages are not illegal.
The places I have been that have jammers do not have signs telling you that jammers are in operation, though they do have many large and prominant signs stating that the operation of cell phones in those areas is prohibited. I’ve never seen warnings around faraday cages either.
Radio transmitters of all sorts are generally marked with a warning due to possible interference with devices like pacemakers. I think restaurants are even required to post a warning sign if they are using microwave ovens. A cell phone jammer might have a warning posted that it is a radio transmitter, but I doubt that the warning would specifically identify it as a cell phone jammer.
An active jammer like that is completely illegal, so that’s going to have to stay in the realm of fantasy. They do sell novelty “machine gun” switches that you can mount on your steering wheel and give yourself a little satisfaction when you are behind someone idiotic on the road, perhaps not as satisfying as a real machine gun but at least you get the sound effects.