Let me join the discussion. Nicolas rightly says that amenability of an action is equivalent to amenability of the orbit equivalence relation and of a.e. stabilizer. It is also true that for a finite invariant measure amenability of the action is equivalent to amenability of the acting group. However, there is no contradiction here as (at least a priori) it might be possible that the orbit equivalence relation of an action of a non-amenable group is still amenable - due to the presence of huge stabilizers (which in this case must necessarily be non-amenable).
I think that the paper by Grigorchuk and Nekrashevych quoted by Kate does provide a requested example. Indeed, they construct (Sections 3 and 4) a non-amenable group which acts faithfully has a faithful self-similar action on a homogeneous rooted tree. This action is self-similar, so that it preserves the uniform measure on the boundary of the tree. Moreover, the orbit equivalence relation is a subrelation (mod 0) of the tail (or co-final in authors' terminology) equivalence relation. Since the latter one is hyperfinite ($\equiv$ amenable), the orbit equivalence relation is also amenable.
