There seem to be two different kinds skill checks.

First, there are the all-or-nothing kind of skill checks with a set DC that you have to beat. You try for it, and if you meet or surpass it, you succeed. There might be several DCs for doing more difficult versions. Ex: Acrobatic - opponent's CMD to pass through a threatened square, and his CMD+5 to actually pass through the square he occupies. You decide what you want to attempt and you succeed or fail.

Then there are skill checks like Knowledge and Perform where you just try to roll as high as possible to see what degree of success you can achieve. With rumors and monsters, the higher the DC, the more information you get. DC 15 gets you common knowledge, DC 20-30 gets you more obscure knowledge. Or Perform, DC 10 for a routine performance and DC 20 for an great performance. You never say, "I'm going to try for a great performance. [rolls a 16] Damn! I missed it. My performance fails." You roll and see how good your performance was.

So this occurs to me last Saturday when I'm GM'ing. A character is trying to climb a tall ladder. DC 5 for climbing at 1/4 speed and DC 10 for climbing at 1/2 speed. Player rolls and ends up with a total of 4 (low roll + 1st level PC). I say "No progress." He says, "No, I fall prone. I was trying to climb at 1/2 speed and missed by 5 or more." He's right by the RAW, but climbing speed seemed like one of the degrees-of-success kind of things rather than an all or nothing. If you make a DC 10, you go at 1/2 speed, if you only make DC 5, 1/4 speed.

I guess my question is, how do you decide if a skill check is all-or-nothing versus degrees-of-success?

I can see what you mean, but that being said, I think this is one of those situations where your players should be better at using the rules to their advantage.

By this I mean using the rules for take-10 (and take-20 for applicable situations).

If he was trying to climb the ladder without any stress or forced circumstances, he should just take-10 and climb it.
Or just GM rule that he climbs it, it's not really hard to do, if you're just a bit focused on what you're doing.
Of course, if a player wants to roleplay an easily distracted and absentminded wizard, you might still opt for the roll... ;)

Now, if this played out during combat, fleeing from enemies or some other stressful situation a take-10 can't be done - and wouldn't make sense either.
And with a low climb skill, the character could end up with a foot on the wrong side of a step and the groin closer than comfort allows to the ladder. Add other circumstances that would raise the chance of missing ones footing; a moist wooden ladder and trying to hurry up while being chased is a recipe for disaster... :D

[edit]
I guess what I'm trying to say is that your examples carries their own penalties if the situation calls for it.
The Ogre King wants a great performance? Don't do it well enough and off with the head.
Knowledge check; again, it's gradual what you get while a complete miss isn't the end of the world.
Climbing a dry ladder in full daylight with no reason to hurry; just do it.
Get chased during a monsoon during night time with arrows flying past your ears and it a whole other ballpark of failures.

For the Climb skill, it strikes me as a trade-off, similar to using the Acrobatics skill to balance on a narrow surface. Namely: Should I "walk" and be relatively safe, or should I "run" and risk falling?

I guess I'd apply the same reasoning to any skill: you can take the slow and safe approach, or the quick and risky approach.

It was actually a combat situation - vs. a couple of giant scorpions - so he couldn't take 10.

But I guess the conclusion that I'm coming to regarding all-or-nothing and degrees-of-success skill checks is that it depends on the risks of failures. Kinda' like retrying a skill check after a failure. Is it possible to have some adverse effect if you actually blow it? Acrobatics - yes. Climb - yes. Knowledge - probably not, unless you make up some rule about remembering wrong information.

Still, I think it's interesting that there really do seem to be two ways of doing skill checks and I've never seen it discussed in any of the books.