Is it possible to build a mechanical version of the basic logic gates AND, OR, XOR and NOT? Is it possible to physically build a the basic logic gates with nuts ans bolts? I'm wondering if it's possible to build a mechanical adder unit.
 A: Yes.  A toy in the 1960s provided geeky kids with flip-flops and programmable logic implemented in plastic, rubber bands and short sections of plastic straws.  It was called the Digi-Comp.  It could be "programmed" to be a 3-bit shift register or counter.  Though it was limited to three flip-flops and three logic sections, in principle it could have had more.  
See, for example, http://alvelda.wordpress.com/2006/08/16/the-toy-that-got-me-started-in-computing/ 
Of course, there is the whole Babbage engine project eons ago.
A: Note: in computing, mechanical device will generally mean any kind of physical device. No so for physicists.  Then a problem is said to be mechanized as long as it can be handled by any kind of physical device (generally an electronic computer).
You can rely on the turing completeness of computers to presume that
anything you can compute can be computed by a mechanical device,
including logic operations.
I am saying "presume", because turing completeness is a slightly
misleading concept for the unwary. The situation is that many models
of what computing means have been developed by top mathematicians and
logicians. They have all been shown equivalent to the model developed
by Alan Turing, the Turing machine (some were actually a bit weaker,
possibly intentionally to capture other properties). So we presume
that is as much as can be done, but that cannot be proved. This is called Church's Thesis (meaning "hypothesis") from Alonzo Church who created the lambda calculus, another major model of computation.
That being said, that are lots of physical devices that mimic directly the
behavior of logical gates, and can be assembled to create more complex
logical devices.  Precisely those devices that are used to make
computers.
The best known ones are based on simple electronics with
transistors. But the first computers were built from gates contructed
with electromechanical relays, and later with tubes, mostly triods
I guess. They were heavy on energy.
Some (rudimentary ones) were built from fluid mechanics, using gas in special circuits intended to
resist very hostile environments. The gas flow would be oriented this way or that way with pressure mechanisms (this is very old memory).
A lot of research is now into light based devices, for greater speed and lower consumption
In all these devices, 0 and 1 are represented by some physical
quantity that ccan take 2 values: voltage, current, pressure ...
This is complemented by memory systems, where other, usually more stable
phenomena are used, such as magnetic orientation.  Variety is probably
even greater historically in memory systems. Mechanical devices were also used to buid memories. For example, around the sixties, there were memories build  from delay lines: mechanical torsion was imparted to one end of the line and would propagate to the other end, while other torsion were imparted behind it; when reaching the other end, the torsion would be read and reinjected at the beginning. It worked like a kind of drum memory.
And yes, these devices can be used to build adders, or many other
types of devices.
About solid logical gates
If you want mechanical gates made with solid components, here is
an example of a one bit adder : http://halfbakedmaker.org/?p=116
I did not check it.
You can simply search the web with: mechanical logic gates and you will find many, mostly toys. Have fun.
As I said in a comment, I do not believe the Babbage engine fits your
request, except in an abstract sense, as it is a decimal and not a
binary device. Now it is possible that some parts of it may be
considered logical gates, but I would not know that without studying
the details.
If you consider solid mechanical devices (Babbage's engine, Curta calculator, Pascal's machine, Leibniz' Step Reckoner) they were all
based on decimal computation. Solid logical gates seem to all be toys or
thought experiments, or at best experimental devices. There are
probably good reasons for that. One that I can see is that mechanical
devices are probably more fragile and more power hungry when they have
more parts. Hence they are probably more effective when each component can
represent a larger number of values, or when you can realize a complex
operations withone or two gears or other mechanical contraptions, rather than decomposing into very elementary primitives.
Another reason is that putting together a large number of gates,
and solid devices may impose a lot of geometric constraints on the way
they communicate, and also on the mechanisms to bring in energy to
activate the gates. Again, reducing the number of parts may make the
problem simpler.
Things are much easier if you have flexible parts, as with devices
composed of gates based
on fluid mechanics, connected by fleible pipes, or electromechanical
gates connected by wires.
A: The answer is an emphatic yes. Essentially this is what Charles Babbage did (look him up on Wikipedia). Also look up his Analytical Engine. This is accepted as the first computer that is Turing Complete. Therefore, by the Church-Turing thesis any computation done by any kind of physical computer can also be done on a mechanical computer. Parts of Babbage's ideas have actually been built but I'm not sure how far the builders have gotten (see plan28.org). However, it is widely accepted that Babbage's concepts are altogether sound - any problems arise from the exacting strictness of the accuracy requirements for the mechanical parts (the mechanical tolerances are tight, as the mechanical engineers would say). 
A related topic is that there is also quite a bit of "thought experiment" interest in reversible mechanical computatation engines. In particular, Charles Bennett invented perfectly reversible mechanical gates whose state could be queried without the expenditure of energy. See "The Thermodynamics of Computation - A Review" by Charles Bennett. Bennett used such mechanical gates to thought-experimentally study the Szilard Engine and to show that Landauer's Limit (the minimum amount of work needed for computation) arises not from the cost of finding out a system's state (as Szilard had assumed) but from the need to continually "forget" former states of the engine.
See also Chris's comment on functional completeness - one or two well-chosen Boolean operators can be combined to get you all the rest.
