(1.) GPS is getting very small and would do a superb job, but the next solution is more liable to appeal.
(2.) A small rigid almost sealed container will lag the outside pressure by an amount determined by the leakage rate and container volume.
Pressure sensors come in absolute and differential versions.
Absolute measure pressure relative to some internal reference.
Differential sensors have two "ports" and measure difference between them,
A pressure sensor with one port inside the container and one port outside will reliably indicate whether you are rising or falling.
If internal pressure is above external pressure the object is rising.
If internal pressure is below external pressure the object is falling.
The indication will be a weighted average of the period for a few time constants leading up to the present moment. eg if a rising object dips briefly and for less than a time constant of the container then rises again the pressure inside would increase briefly due to the dip but not enough to flip over into falling mode.
Atmospheric pressure halves about every 4500 metres in a logarithmic manner
Some quick figuring which may be woefully wrong suggests that nearish sea-level a 1 metre vertical separation gives about 14 Pa difference in pressure.
1 atmosphere = 100,000 Pa = 100 kPa so 14 Pa ~= 0.014% of an atmosphere.
Despite being small the difference should be able to be reliably detected.
A look at Digikey prices suggests that a minimum price of around $25 is required. Maybe more for what you need.(But see Sparkfun offering below for about $9).
Here is an "off the cuff" possible solution.
Use a small rigid container with a controlled leak. Size tbd.
Make a hold in one wall perhaps 20mm across. Size tbd.
Place a very light diaphragm across hole in wall with "enough " slack in it so that it domes in or out under pressure difference.
It should be possible to get an extremely low pressure indication of direction of pressure difference. P inside greater = rising - dome out. Pinside smaller = falling, dome in.
Detect dome position optically.
I tried the diaphragm method with no visible results - I think.
I used a reasonably rigid 500 ml pill bottle and used a sheet of "glad wrap" as the diaphragm. Gladwrap was pulled over opening with some slack in it and fastened with several rubber bands around neck. Container was carried up street a height of about 10 metres (top of road from my house). Photos were taken by street lamp and flash at top and bottom. Visual examination in-camera showed no obvious change. Subsequent examination on PC screen may show otherwise. So ...
Method "needs work" :-). I'm sure it can be made to work BUT a commercial sensor is a lot easier.
The TI Chronos watches are specialed at half price by TI occasionally
Re Bosch BMP085 sensor as suggested by Caleb - data sheet here
This is "just" suitable for the job.
Variation in pressure is around 12 Pa/m- varies with altitude.
Bosch datasheet use hPa = HectoPascal - very naughty non SI unit !!!.
1 hPa = 100 Pa = 100 N/m^2.
Bosch unit has noise level - which sets usable sensitivity, of 6 Pa = 0.5m and in low power mode and 3 pa = 0.25m in low noise mode.
So assessment to about 1 m should be viable [tm] in this application.
$US9 from Sparkfun here and
$20 on PCB with 2Rs and cap here