To elaborate a bit more on the previous answers, computing the auto-correlation of a signal of length $N$ results in a (sampled) auto-correlation of size $2N-1$. Well, actually, it should be infinite, but the auto-correlation outside $[-(N-1), N-1]$ equals $0$ anyway.
Now, you desire to use the discrete Fourier transform (DFT) to compute it, and the formula is indeed the inverse DFT of the squared magnitude of the DFT of your signal. But think about it: if we take it the other way around and compute the DFT of the auto-correlation, you end up with a spectrum of size $2N-1$, if you don't want to lose samples in the way! That spectrum therefore has to be of size $2N-1$, and that's the reason why you need to zero-pad your time-domain signal up to $2N-1$, compute the DFT (on $2N-1$ points), and proceed with it.
Another way of seeing this is to analyze what happens if you compute the DFT on $N$ points: this is equivalent to downsampling your (continuous frequency) discrete time Fourier transform (DTFT). Retrieving the auto-correlation, which should be of size $2N-1$, with an under-sampled spectrum of size $N$ therefore leads to time aliasing (the circularity pichenettes was talking about), which explains why you have this symmetrical pattern in the "right hand side" if your output.
Actually, the code provided by Hilmar also works, because as long as you zero-pad up to more than a size of $N-1$ (in his case, he computes an FT of size $N$), you "over-sample" your FT, and you still get your $2N-1$ "useful" samples (the other ones should be $0$s). So, for efficiency, just zero-pad to $2N-1$, that's all what you need (well, perhaps you'd better zero-pad up to the next power of 2 of $2N-1$, if you use FFTs).
In short: you should have done this (to be adapted to your programming language):
autocorr = ifft( complex( abs(fft(inputData, n=2*N-1))**2, 0 ) )
Or in MATLAB:
autocorr = ifft(abs(fft(inputData, 2*N-1)).^2)