CO adsorption on small cationic, neutral, and anionic Au-n (n=1-6) clusters has been investigated using density functional theory in the generalized gradient approximation. Among various possible CO adsorption sites, the on-top (one-fold coordinated) is found to be the most favorable one, irrespective of the charge state of the cluster. In addition, planar structures are preferred by both the bare and the CO-adsorbed clusters. The adsorption energies of CO on the cationic clusters are generally greater than those on the neutral and anionic complexes, and decrease with size. The adsorption energies on the anions, instead, increase with cluster size and reach a local maximum at Au5CO-, in agreement with recent experiment. The differences in adsorption energies for the different charge states decrease with increasing cluster size.