What is an obviously coordinate-independent description of the Chevellay-Eilenberg complex for a Lie algebroid? I've read in many places, including the n-Lab page, that a Lie algebroid (which I think of as in the first definition on the n-Lab page) is the same as a vector bundle $A \to X$ and a (properties?) derivation that makes $\Gamma(\wedge^\bullet A^*)$ into a cochain complex (here $A^* \to X$ is the dual vector bundle).  One motivation for considering this cochain complex is that in the two extremes $A = {\rm T}X$ and $X = \{\rm pt\}$, the complex becomes respectively the deRham complex and the Chevellay-Eilenberg complex for a Lie algebra.  My motivation has something to do with understanding BRST-type arguments.
I only partially understand this relationship.  Given a trivialized vector bundle $(V\times X)\to X$ with a differential $d$ on $\mathcal C^\infty (X,\wedge^\bullet V)$, then I can define a Lie algebroid structure on $V\times X \to X$ — the Lie algebroid axioms are equivalent to $d^2 = 0$.  Conversely, given a Lie algebroid $A\to X$ with $A$ trivialized as a bundle, I know how to interpret the standard formulas for the differential on $\Gamma(\wedge^\bullet A^*)$ — n-Lab, for example, reproduces the standard formula.
But I do not know how to interpret the formula defining the differential without trivializing the bundle, and my interpretation, as far as I can tell, depends on the trivialization (the fiber coordinates).  At least, I've tried to check that my interpretation of the formula (which does get the above statements about $d^2 = 0$, etc., correct) is invariant under changing the trivialization, and I have failed.  Hence:

What is a totally invariant description of the Lie algebroid CE chain complex?

Better: is there such a description that is simultaneously useful for explicit calculations?
 A: I believe an approach that works is to define the Chevalley-Eilenberg complex as a kind of `Koszul complex over the ring of functions'.  The enveloping algebra $U$ is relatively quadratic over the ring of functions $O$, and so you can define a quadratic dual algebra $U^\perp$ in analog with the absolute case (when there is a field in degree zero).  The corresponding Koszul boundary then squares to zero by a simple argument, and a slightly harder argument shows the Koszul complex is a resolution of $O$ as a left $U$-module.
I worked this out in my paper on the Beilison equivalence for Lie algebroids.  The section you want is the first couple of pages of section 4.
EDIT:  After rereading your question, it sounds like you are more interested in how to recover the standard Lie algebroid structure (the 'bracket' and 'anchor map') from the CE complex.  These should be gotten directly from the zero degree differential:
$$ O\rightarrow L^* $$
and the first degree differential
$$ L^* \rightarrow L^* \wedge L^* $$
The dual of the first map gives a derivation for every element of $L$ by the Leibniz rule, so it defines the anchor map $L\rightarrow T_X$.  The dual of the second map gives a map $L\wedge L \rightarrow L$ which defines the Lie bracket on $L$.  
The condition that the $d$ satisfies the Leibniz rule for the product of a degree zero element and a degree one element in $\Lambda^\bullet_X L$ is gives the Leibniz condition for the Lie algebroid, and the condition that $d^2$ is zero on degree 1 elements gives the Jacobi identity.
Is this the kind of answer you were looking for?
Oh, I should mention that this argument, the nLab page, and my paper assume $L$ is a vector bundle; some other sources might not.  The result you mention (the differential on $\Lambda^\bullet L^*$ being equivalent to a Lie algebroid structure) is not true in that context.
A: I think that the relation is that if $\psi\colon A \to TM$ is the action of the algebroid, then we have that $df(a)=\psi(a)(f)$ for $f$ in degree zero of the CE complex and $a\in\Gamma(A)$ and $d\omega(a,b)=\omega([a,b])+\psi(a)(\omega(b))-\psi(b)(\omega(a))$, where $\omega\in\Gamma(A^\ast)$ and $a,b\in\Gamma(A)$. One then extends $d$ to the full CE complex by Leibniz' rule just as for the de Rham complex (and $d^2=0$ comes from the Jacobi identity).
A: Let me elaborate on Greg's excellent answer.
First ake the enveloping algebra $U(A)$ of the Lie algebroid - this is a sheaf of algebras generated by the algebroid and functions satisfying the standard relations (Leibniz rule, commutation rule in the algebroid). In the two extreme cases you mention you get the sheaf of differential operators and the enveloping algebra of a Lie algebra.
One can then consider the structure sheaf $\mathcal O$ as a module for $U(A)$, and take the sheaf Ext complex $Ext_{U(A)}(\mathcal O, \mathcal O)$. This is a sheaf of differential graded algebras, and is an abstract form of the Chevalley-Eilenberg complex (ie the latter is a concrete model for the former). The functor $Ext_{U(A)}(\mathcal O, -)$ is the de Rham functor (Koszul duality) from modules for the algebroid to dg modules for its C-E complex, and is an equivalence of derived categories of reasonable (ie not too big) modules.
