I hesitate to comment on this one because CAI's are almost a religion with some folks and their value has changed over time. But, here goes...
In addition to what
USStrongman said about the ECU/EFI issues, there's another thing to pay attention to if you modify the intake: The oscillation of half of the pistons doing an intake valve cycle for each revolution of the crank, a poor intake design can create a (loud, roaring) standing (stationary) pressure wave at the open end of the intake. This standing wave works against the airflow, so, more recently (at least post-2002) automotive engineers have started adding resonance chambers on the intake carefully sized to reduce/prevent the formation of the standing wave allowing for smoother (quieter, but faster/more consistent) airflow into the intake. (Experiment with your home/shop vacuum cleaner hose: when it's unobstructed, you hear a smooth continuous 'whoosh' at the open end of the hose, but when you alternately cover/uncover the end with your hand, you hear a 'thumping')
If the vehicle is older and has no ECU, and no resonance chambers, a modern cold air intake will probably be helpful. Most of the gains will be at RPMs between idle and the bottom of the powerband.
If the vehicle is older and has an ECU but no resonance chambers on the intake, adding a well designed modern intake that pulls colder air than your current intake *might* gain you a little horsepower at RPMs between idle and the bottom of the powerband - though it's extremely unlikely to make a significant change to the peak horsepower.
In a newer vehicle with resonance chambers, pick carefully and remember that a loud roar at the intake can indicate a standing pressure wave blocking air induction. If you have an OBDII reader, you might be able to watch the mass airflow sensor at several RPM points to get an idea of whether you're actually feeding more or less air to the engine.
As always, more power = more fuel = lower fuel efficiency.
The exhaust side is a little simpler - the design trade-offs are flow and noise - a high-flow cat-back exhaust system will be louder than the stock system, but as above, you might gain a little horsepower, again mostly isolated to RPMs between idle and the bottom of the powerband, (especially so for newer vehicles).