Think of the levels adjustment as a mathematical function; you pass in something (input), it does something to it, and returns a result (output). The input is the existing (original) value and the output is the result after the adjustment has been applied.

If you open an image and apply a levels adjustment layer and look at the input sliders, first at the black slider, this specifies which input values should be black. Anything to the left of the slider is going to be black. Basically, the camera picked up some information, but you don't want it, you want those pixels black (happens a lot of you expose-to-the-right, or ETTR). Similarly with the white slider, you're specifying the threshold of input data that should be treated as white.

The middle slider is your mid point. I'm not sure if it's 18% grey or 50% grey, but wherever that slider is should be some medium brightness. So looking at the histogram, as you move the slider left you're saying whatever is right above it should be medium and everything to the right is brighter. So as you move the slider left, things that were previously darker than medium are now brighter than medium and vice versa as you move right.

Now, output levels. This is saying the final values should fall within a certain range. Default is between white and black (pretty all encompasing), but you can decide to limit it to a certain range of greys by moving either of the sliders inward.

Note that levels is almost certainly a simplified GUI to the curves adjustment layer (I would love for someone to confirm this). Using curves you can do the same as levels fairly simply, albeit in a different way, and expand to have more control over the curve (think levels with multiple midpoint sliders).