Why is a piece of paper lifted upward even when blown below? According to Wikipedia,

A correct explanation of why the paper rises would observe that the
  plume follows the curve of the paper and that a curved streamline will
  develop a pressure gradient perpendicular to the direction of flow,
  with the lower pressure on the inside of the curve. Bernoulli's
  principle predicts that the decrease in pressure is associated with an
  increase in speed, i.e. that as the air passes over the paper it
  speeds up and moves faster than it was moving when it left the
  demonstrator's mouth. But this is not apparent from the
  demonstration.



*

*Why does the air speed up while passing over the paper?



the plume follows the curve of the paper



*Does that mean, the paper cannot be planer and has to be curved for this effect to occur?

*How does this explain how the paper will move upward when one blows along the bottom of the paper?
 A: Before I start the answer, I'd like to point out that Bernoulli's principle is not applicable directly when you're comparing air flow from two different sources ( or two different flow fields, according to Wikipedia ). It only relates the speed and pressure of air within a single flow field.
Now let's consider the first case where you blow over the sheet of paper. The paper would not rise if it were flat, even though you are blowing air across the top of it at a furious rate. Bernoulli's principle does not apply directly in this case. This is because the air on the two sides of the paper did not start out from the same source. The air on the bottom is air from the room, but the air on the top came from your mouth where you actually increased its speed without decreasing its pressure by forcing it out of your mouth. As a result the air on both sides of the flat paper actually has the same pressure, even though the air on the top is moving faster. The reason that a curved piece of paper does rise is that the air from your mouth speeds up even more as it follows the curve of the paper, which in turn lowers the pressure according to Bernoulli's principle.
If Bernoulli's principle were to hold true in the first case, it would then imply that the paper would droop downward in the second case, when air is blown below the paper. But this is clearly not the case. The upward pressure gradient in this downward-curving flow adds to the atmospheric pressure at the lower surface of the paper. This resulting pressure gradient is the source of lift in the second case. I hope this answers your question.
Reference: Wikipedia
EDIT - A formal derivation of the mathematical relation between curved streamlines and pressure gradients can be found here: https://ocw.mit.edu/courses/aeronautics-and-astronautics/16-01-unified-engineering-i-ii-iii-iv-fall-2005-spring-2006/fluid-mechanics/f20_fall.pdf
EDIT 2 - Lift is also generated by the Coanda effect. Here a couple of links:
How is lift generated due to Coanda effect?
http://en.wikipedia.org/wiki/Coand%C4%83_effect
A: Under the action of gravity, the paper will bend downward. Under this condition, blowing on the upper surface of the paper will produce a pressure gradient perpendicular to the paper. This cannot be explained by Bernoulli's theorem.
