I often receive emails about adding a chip or changing the exhaust, all wanting to know what upgrade is worth the money and what is the expected HP gain.
This page will give you the do's and don'ts for your BMW E34 - E32 - E28.

I started from the easier add on to the difficult and pricey upgrades

The performance chip is the "best bang for the buck" for $250, you cannot go wrong. 30 min later you will have between 15 - 40 more Hp under the hood.
The OEM chips are programmed to work with the weaker gas octane and to reduce fuel consumption.
Changing the chip will raise the rev limit and remove the top speed limit.

BmwE34.net recommendation: Jim Conforti chip.
HP gains: 15 to 40 Hp
Avg. Price: $250.

There is a big controversy about replacement filters. The E34 air box is well designed and isn't restrictive. It shields the filter well against the warm air of the engine.
Changing the filter will make the exhaust note deeper. Maybe a little increase of acceleration and it will be the last time that you'll buy an air filter (if you clean and oil it).
I must warn you that some people think that the K&N type filters do not filter the air as good as the stock filter and might harm your engine.

BmwE34.net recommendation: If you really have to, get a K&N filter replacement and remember to clean it.
HP gains: -3 to 0.5Hp (yes it is a minus 3)
Avg. Price: $40 (filter) - 150 (cold air).

Pure waste of money, maybe you can buy them if you want a touch of colour in the engine compartments. Changing the well designed OEM wires with "performance" ones is asking for trouble. Your engine might run worse.

BmwE34.net recommendation: Stick to OEM.
HP gains: 0 Hp
Avg. Price: $170.

Sorry, but you don't have a Honda. There is little to no gain by changing the exhaust system.
The change could be justified if your exhaust is in bad shape or if you want a deeper note.
As I already said: " no engine makes more power with a muffler than an open header exhaust. " But I strongly discourage anyone to do that.
The muffler out of the way, what about the catalytic converter? Again, the BMW cat. is non restrictive. And it is illegal to remove the catalytic converter.

BmwE34.net recommendation: get nice chrome tips instead, or get stainless steel if you keep the E34/E32 for ever.
HP gains: 0 to 3hp
Avg. Price: from $200 up.

Headers makes the exhaust gases come together more smoothly than stock before entering the cat.
They can be expensive (up to $1000), but there is still a couple of RD headers on ebay sometimes.

BmwE34.net recommendation: Definitively get it if you have a modified intake with a polished cylinder head.
HP gains: 7 to 30Hp (with forced admission)
Avg. Price: from 600 up.

The Power principle is to enter as much (cold) air as possible into the engine. So you could think that a bigger throttle body should help right? Yes, only if you have a MAF (see below), else it is a waste of money because the Air Flow Meter is very restrictive.

Forget about the Dinan and other (BMP) overpriced throttle bodies, take yours to a local auto machine shop. They can do as good as a job as the professional tuners for way less money.
Check also in Bimmer magazine: Ed Mazula's ad (CA) (800) 792-9338. Next day service.

BmwE34.net recommendation: Definitively get it if you have a modified intake with a polished cylinder head.
HP gains: 0 to 1.5?Hp (with MAF)
Avg. Price: from $200 up.

This is another interesting upgrade. The E34 MAF (at least in the M30 engine) is quite restrictive. The stock Air Flow Meter (AFM) is the large metal box on top of the engine valve cover. One end takes the air from the air box, the other is connected the the throttle body.
The principle is a metal door monitoring the flow through the AFM. As you can imagine, this setup is very restrictive.
The MAF uses a heated wire to monitor the flow through a tube which almost create no restriction. Only problem is the price: $1000 for split second and $500 for Modern Performance.

BmwE34.net recommendation: A good power upgrade (I am working on a setup for less than $400).
HP gains: 5 to 10Hp
Avg. Price: from $400 up.

This is a great upgrade if you have added a turbo or supercharger to your car. Or else, you need a highly modified engine to gain from this upgrade.

Same comments for bigger injectors.

BmwE34.net recommendation: Most of us don't need that.
HP gains: 0 to 2?Hp
Avg. Price: from $170 up.

This is a great upgrade, a must do if you have to remove the intake to change the gasket or rebuild the cylinder head. The intake is restricted and doesn't match the holes in the cylinder head.
This upgrade + headers is a great combo. This will give you some extra power in the upper RPM range.

Don't go Dinan, as this is waste of money. Get a local shop to modify it for you.

BmwE34.net recommendation: Easy and cheap modification.
HP gains: 0 to 2?Hp
Avg. Price: from $100 up.

This isn't an easy upgrade, but perfect if you are having some work done on your cylinder head. There is a couple of different camshaft profiles you can choose from. The Schrick Cam delivers a noticeable increase in power, especially above 3000 rpm where the engine seems to come on cam. This is an improvement over the standard E34 engine which seems to come on cam at 3400 rpm. And of course, above 4000 rpm's the Cam really makes itself felt (high performance springs and retainers are recommended).

BmwE34.net recommendation: Go for it if you have the extra cash.
HP gains: 5 to 10Hp
Avg. Price: from $400 up.

This isn't a cheap upgrade, and not an easy one. A used differential cost between $500 and $900 and you still have to install it on your car...
For example: a 3.91LSD diff. from a 525iA installed to replace the stock 3.46LSD in the 535i will give you a mileage loss of about 2/3 mpg on the highway. But it is more than justified by the drastic increase in acceleration.

The 535i 3.46 doesn't seem to fit the '95 525 5-speed.

BmwE34.net recommendation: Great upgrade for acceleration increase.
HP gains: 0 to ?Hp
Avg. Price: from $500 up.

This is another great upgrade because the dual mass flywheel in your E34 is probably making some weird noise each time you shut the car off.
A lighter rotating mass will give your E34 better acceleration and faster throttle response. The new flywheel might affect your idle.

BmwE34.net recommendation: Perfect if you have your clutch changed.
HP gains: 0 to 2?Hp
Avg. Price: from $600up.

Now, what is left?
At reasonable cost, not much... Modification of the Automatic Transmission to a higher stall Torque Converter. And if that's not enough, and you have money left, then look at either an M5 Engine Conversion or Supercharger/Turbocharger installation, or a Supercharged/Turbocharged M5.
Me... I keep dreaming of a BMW E34 M5 Bi-turbo....

The following results are from a Dyno Test on an E34 535i with 3.73 Diff Ratio, Free Flow Exhaust, K&N Air Filter and a Jim.C. Chip.

The test results:
Maximum HP: Up to 229HP (171kW) from 208HP (155kW)
Maximum Torque: Up to 243lb/ft (332Nm) from 223lb/ft (305Nm)
Information from Richard Nott

Some information about exhaust systems from Matt Evans:

no engine makes more power with a muffler than an open header exhaust.
This could be construed as saying mufflers never help power. I believe this could be more accurately put: if you just lopped off your exhaust after the headers, you would very likely get a torque _and_ power decrease.
A subtle amount of backpressure of course helps torque (while too much limits top end power, of course). However, just as header length and tuning helps with gas scavenging and optimizing power at a certain rev range, the over all length of the system is an important consideration in exhaust design. Simply replacing the well designed OEM exhaust system with a random cobbling of big mandrel bent pipes is very unlikely to give good results. The best combination will be properly tuned headers, and the right collector/crossover pipes, and finally the mufflers/horns/what have you that bring the system to the correct total length.

Optimizing the entire system for weight, cost, performance, sound, and space requirements is obviously tricky. I don't know even a faction of the fluid dynamics required to do even an amateurish job at improving upon the BMW design. Most people don't. The only significant improvement on the stock BMW systems are going to properly designed headers in place of the EPA friendly manifolds, or switching to an exhaust of similar design and layout, but made of lighter materials, as you point out.