The intuition is that both give the existence of an intangible object.
The axiom of choice gives us a choice function, which is a way to choose an element from each set of a certain family; whereas Zorn's lemma gives us the existence of a maximal element, given the partial order satisfies some property.
The idea behind the proof is not very difficult if you are familiar with how are functions represented in set theory, and with transfinite recursion (which requires you to be at least a little bit comfortable around ordinals).
Assuming the axiom of choice, we essentially traverse the partial order in search for a maximal element. The choice function is a guide on how to proceed at each step. And we can prove that it is impossible that we never find a maximal element.
Assuming Zorn's lemma, and given some family of non-empty sets, we consider the partial order of partial choice functions (functions which choose from a subfamily) ordered by extension (or set inclusion). We can quite easily prove that this partial order satisfies the condition for Zorn's lemma, and a maximal element is necessarily a choice function itself.
As Andre noted, and in fact much more, there are many, many equivalents to the axiom of choice. Wherever intangible objects come into play, the axiom of choice is likely to be found, and some equivalent is likely to be formulated.
The most common equivalent is the well-ordering principle. We say that a linear order is a well-order if every non-empty set has a minimal element. Like the natural numbers. It turns out that the axiom of choice is equivalent to the statement "Every set can be well-ordered", that is to say that for every given set, there is a linear order on that set which is a well-order.