Starting off with a little physics: An airfoil (wing) generates lift due to pressure variations created by the shape of the wing. Bernoulli's equation which models the laminate flow of a fluid (or in this case a gas) though a restriction is: P+(rho*V^2)/2 = n (Pressure + (density x Velocity squared) divided by 2 = some constant. I'll spare you the entire derivation but the end result is the equation for lift which is:
Lift = CI * (rho*V^2)/2 * A
CI = Coefficient of lift
rho = Air density
V = Air Velocity
A = Area of the wing
In essence this shows that the faster air is forced over the top of the wing, the lower the air pressure becomes above the wing. Since the air pressure under the wing remains high due to a relatively flat surface, and that nature will look to fill a void, the wing is sucked up into the low pressure (or, if it is easier to wrap your head around the high pressure below the wing pushes it up into the low pressure above the wing (Newtonian view)) thus, we have lift.
(By the way, the Newtonian view and the Bernoulli's view are not mutually exclusive, they are two different approaches that show the same thing... but I digress and that is a whole other ball of wax)
Now, to the meat of your question: As we increase the angle of attack(AOA), lift increases due to a higher coefficient of lift. This would seem to suggest that your initial supposition is correct after all, higher AOA mean greater coefficient of lift but if we look back at our equation we see that the velocity of the airflow over the wing is critical to lift. If we take an idealized look at the airflow as it separates from the wing(Critical Angle of Attack), the air velocity over the wing drops to zero which means we have: Lift = CI((rho*0.0)/2)*A = 0.0, no lift which causes a stall.
As to the second part of your question, why does the drag increase? A fairly straight forward application of Newton's laws tells us what is going on. As the AOA increases and increasing large surface area of the wing is exposed to the relative wind. Combine that with increasing vorticities behind the trailing edge of your wing, creating a low pressure area, and you have increasing drag.
Hope that helps and best of luck in your flying.