I was wondering how to parse/decode Audio files (like mp3s) with the XNA framework or C#.  I recently tried the game Audiosurf and was intrigued by how it created levels live using songs.  I want to know how they decoded the files and read the different types of sounds and stuff to make the level.  What can I use to decode audo files?

According to Wikipedia, Audiosurf uses an offline build step to analyse the music, rather than doing this on the fly:

"Each music file imported to the game by the user is first analyzed by the game engine, and an ASH file (containing the dynamics of the sounds and how the track and blocks are arranged) associated to the music is created and saved (typically around 30 kilobytes)."

There is nothing built into the XNA Framework to do this, but you could roll your own if you have the necessary signal processing experience, or can find libraries to implement the hard parts. I suspect they first use an MP3 decoder to convert the audio to PCM format, then run an FFT over that to extract frequency bands, probably in conjunction with some kind of (maybe per band?) beat matching algorithm.

Beat matching can be done in several ways:
Notch filters with envelope followers
Autoconvolution
FFT based methods

However, the bigger problem is that XNA doesn't allow you to stream any audio that hasn't gone through the build pipeline. Thus, the MP3 files have to be built into XMA files (for Xbox) or ADPCM files (for Windows) to be playable in XNA GS 2.0. Allegedly, we're getting MP3 and WMA playback in the 3.0 version, but they haven't yet announced whether there will be a "sample clock" value that will allow you to correlate playback to position in the song.

hmmm ok, so would I have to use a wave file only? I wouldn't mind that, I just want to know how to decode an audio file to get the necessary info off of it. 

EDIT: what is FFT? I did a quick google search and ended up with the Fourier Transform.  How does this help me and how do I implement this in c#? I'm sorry for my lack of knowledge, this is the first time I have tried to mess with audio files (away from simply playing them). 

FFT stands for Fast Fourier Transform: this is a mathematical operation which converts a sampled waveform into frequency information.

I have to warn you, this sort of audio analysis is not going to be an easy task. It is a complex job, requires some advanced mathematics, and there is nothing built into the XNA Framework to help you with it. If you want to implement this yourself, you're going to have to do some serious learning about computer audio and signal processing (there are plenty of books about this: it's a huge topic!). Otherwise you could try to find an existing library that implements this kind of analysis for you. I have no idea if such a thing exists in a reusable or freely available form, though.

I found some links online that help a little bit.  Can I use basic c# libraries and c# addons?  How compatible are c# libraries and the XNA framework (I know XNA is built off of c# but do know that certain pieces are incompatible).  Could I use c# to allow the user to choose the music file? (as opposed to preloading it into XNA)?

On Windows there is nothing that is really off limits. You can use any .NET library you want and make wrappers for any native library. There is no such thing as an incompatible library on that platform.

For the Xbox the only rule is that all libraries you use must be 100% managed code so no wrappers on native libraries. But if you find a pure managed way to handle this, then sure you can use it with your Xbox game as well.

However it seems that something like this would be worthless on Xbox since you don't have access to the Xbox's music library so I'd say just stick with Windows for now.