We present the results of a uniform, high-precision spectroscopic metallicity study of 136 G-type stars from the Anglo-Australian Planet Search, 20 of which are known to harbour extrasolar planets (as at 2005 July). Abundances in Fe, C, Na, Al, Si, Ca, Ti and Ni are presented, along with Stroemgen photometric metallicities. This study is one of several recent studies examining the metallicities of a sample of planet-host and non-planet-host stars that were obtained from a single sample, and analysed in an identical manner, providing an unbiased estimate of the metallicity trends for planet-bearing stars. We find that non-parametric tests of the distribution of metallicities for planet-host and non-planet-host stars are significantly different at a level of 99.4 per cent confidence. We confirm the previously observed trend for planet-host stars to have higher mean metallicities than non-planet-host stars, with a mean metallicity for planet-host stars of [Fe/H]=0.06+/-0.03dex compared with [Fe/H]=0.09+/-0.01dex for non-host-stars in our sample. This enrichment is also seen in the other elements studied. Based on our findings, we suggest that this observed enhancement is more likely a relic of the original gas cloud from which the star and its planets formed, rather than being due to 'pollution' of the stellar photosphere.