The general proof is suggested by the argument in the two-dimensional case. There, for each possible direction s for the cut, we clearly have, for each region, a line in direction s bisecting that region. But the two lines for the two regions are offset by some distance d(s). We'd like to find a direction with d(s) = 0.
Note that, if we have rotate our direction by 180 degrees, we get back to the same pair of bisecting lines, but they now have the opposite orientation. Adopting the convention that the distance d between the lines is a signed quantity depending on the orientation, we see that d(s+180) = -d(s). Thus it is clear that d is neither always positive nor always negative. Since d is a continuous function, by the intermediate-value theorem it must achieve a value of 0 for some direction.
Thinking of the circle of directions as the unit circle in the plane, we might write -s instead of s+180 for the opposite direction. Thus we have a function d from the circle of directions to the real numbers, with the property that antipodal points map to negatives of each other: d(-s) = -d(s). Such a function must be zero somewhere.
In three dimensions, we can think of a direction s as a point on the sphere S2; given s we cut each of our regions in half with a plane normal to the ray from the origin to s. With three regions, there are now three bisecting planes, and thus two distances between them. (It doesn't really matter which pairs we pick to measure distance between.) Thus we have a function d from the two-sphere to the plane (pairs of real numbers).
Again, if we move from direction s to the opposite direction -s (the antipodal point on the sphere), the bisecting planes will be the same, but with opposite orientation. Thus each of the distances again gets negated. That is, we have a function from S2 to R2 with the property that antipodal points map to negatives of each other: d(-s) = -d(s).
The Ham-Sandwich theorem claims that this function must map some point on the sphere to the origin. This is a two-dimensional analog of the intermediate-value theorem; it is the two-dimensional case of the Borsuk-Ulam theorem.
The Borsuk-Ulam theorem in general dimensions can be stated in a number of ways but always deals with a map d from sphere to sphere or from sphere to euclidean space which is odd, meaning that d(-s)=-d(s). Another way to describe this property is to say that d is equivariant with respect to the antipodal map (negation).
A nice discussion of the Borsuk-Ulam theorem can be found in Section 2.6 of Guillemin and Pollack's book Differential Topology. Here we will explain the different formulations, and their connections with each other and with the Ham-Sandwich theorem.
One formulation of Borsuk-Ulam says that an odd map from Sn to Rn+1 whose image does not contain the origin must in fact have nonzero mod-2 winding number around the origin.
This means (by definition) exactly that, if we replace d by the map d/|d| from Sn to itself (which will also be odd), it will have odd degree. (The mod-2 degree of a map between compact manifolds is the number of preimages of a generic point.) Thus an equivalent statement of the theorem is that any odd map from Sn to itself has odd degree, and thus in particular will be onto.
An immediate corollary is that there is no odd map from Sn to Sn-1. For any such map could be composed with the inclusion of Sn-1 into Sn to give an odd map whose image was contained in the equator.
An equivalent corollary says that an odd map from Sn to Rn must have the origin as a value somewhere. For if not, we could replace d by d/|d| and get an odd map to Sn-1.
Another statement of the corollary says that given any function f from Sn to Rn, there is a pair of antipodal points where the function values are equal. To prove this, let d(s) = f(s) - f(-s).
This last corollary has interesting consequences. For instance, at any time there is some pair of antipodal points on earth where the temperature and pressure are exactly the same. It is also a nice way to see that the n-sphere is not homeomorphic to any subset of euclidean n-space. For instance there is no way to make a (one-to-one) map of the earth on a planar piece of paper without ripping the image somewhere.
As was suggested by the discussion in two and three dimensions, it is the second corollary (that any odd map from Sn-1 to Rn-1 must have the origin as a value somewhere) which proves the Ham-Sandwich Theorem. For if we have n regions in Rn, then given a direction s in Sn-1, we can find planes in that direction which slice the regions in half. If d measures the n-1 signed distances between these planes, then d is an odd map from Sn-1 to Rn-1. The usual proof of the theorem is by induction.