To me, the simplest would be to run a line in directly to an analog port on the Arduino, but you would only be able to get volume information. Ashley’s suggestion (see Sparkfun Spectrum Shield as an example) would give you frequency information as well. Simon’s would be a lot more complex.
i have successfully done it with both the msgeq7 and on-board processing with a pro mini. They both have good points and bad. msgeq7 is ok, the bands are split nicely, it doesn’t use all the CPU, the circuit is relatively simple and it can be wired direct with a standard line-in (possibly dubious but worked for my setup with no issues!). it’s only 7 bands but they’re nicely selected. onboard fft i did with a promini, i think this means it can work with a micro too, i’ve used more than one library for this, the fastest being not FFT but FHT - http://wiki.openmusiclabs.com/wiki/ArduinoFHT this uses lots of cpu but worked fine with both TM1809 and WS2812 pixels, i got 64 bands using 60 lights at at least 20fps if i remember right - pretty good! I did find it harder to make it look musically nice and also threw away a lot of bands that were too noisy or quiet (bottom 1-2 and top quarter or so respectively). The major plus here is that it’s all done in software, no extra hardware needed beyond an audio input and the speed is still good enough to look very smooth.
I just realised i’ve totally overanswered and you may not even want the complexity of different bands, as Andrew says above then line in -> analog in pin works ok with a wee bit of averaging i’ve found, great if you want to treat all the lights with the same brightness but it’s just not quite as visually interesting. currently i don’t use either of these and use a teensy 3.1 and audio shield but that’s for massive runs of pixels and overkill here. one other tip is that if mounting inside a computer you may well be able to use a lineout header on your soundcard/motherboard which can make things very easy as you can use 2 pairs of female-female socket breadboard style leads, check your manuals!
I don’t think Teensy is overkill for anything— it’s a far better board to start with — anyone still using Arduino stuff should seriously consider — the cost difference is tiny but the benefits huge.