When we use the levels adjustment layer we can see in the settings two main sliders: the first, with a histrogram, is called "input levels" (even if is not written), the second is called "output levels". Why "input" and "output"?
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).
Because that is what they are. Effects have to be applied in an order. Input levels are adjustments to the levels that are coming in to the system. Output levels are adjustments to levels going out of the system.
For example, perhaps on the input, a medium grey is actually what we want to be the darkest part of the image, so we set the input black point to that medium grey. Now all input's that are that medium grey or darker are pure black. We've removed all detail darker than it.
But lets say we don't actually want any of the image to be pure black, we can adjust the output level so that pure black after the input levels is actually a medium dark grey. This will make it so that everything that was black is now a medium dark grey and the rest of the levels will be spread out over the remaining range between the output level black and output level white.
In other words, the input level black and white determine what value of input is pure black and what value is pure white. The output level black and white determine what color should be used for the black point and white point of the final image.