Creatures without hands don't need to use hands to climb.
Almost all rules for skills (and pretty much everything else) are given in relation to the PCs, who are almost always humanoid. Thus, in most circumstances the creature using the climbing skill rules has 2 arms and 2 legs and will be climbing with them.
Non-humanoid characters can't follow these rules, just like you pointed out: spiders don't have hands but can climb, so there must exist an exception for them. Since they have a climb speed they are using something other than their hands to climb. It doesn't totally work with the rules, but that is why we have GMs and not computers.
From the SRD:
- Climb Speed A creature with a climb speed has a +8 racial bonus on all Climb checks. The creature must make a Climb check to climb any wall or slope with a DC higher than 0, but it can always choose to take 10, even if rushed or threatened while climbing. If a creature with a climb speed chooses an accelerated climb (see above), it moves at double its climb speed (or at its land speed, whichever is slower) and makes a single Climb check at a –5 penalty. Such a creature retains its Dexterity bonus to Armor Class (if any) while climbing, and opponents get no special bonus to their attacks against it. It cannot, however, use the run action while climbing.
Note that with a Str score of 10 with no ranks in Climb, any creature with a climb speed can take 10 and get a total of at least 18* for a Climb check.
So according to the rules, yes, spiders and eidolons and other things with climb speeds should make checks to Climb, but in reality they would be redundant rolls because such creatures almost always have enough bonuses to their Climb skill to automatically succeed**. If circumstances forced enough penalties to their Climb, then actually rolling would be a good idea.
*For reference:
DC 15: Any surface with adequate handholds and footholds (natural or artificial), such as a very rough natural rock surface or a tree, or an unknotted rope, or pulling yourself up when dangling by your hands.
DC 20: An uneven surface with some narrow handholds and footholds, such as a typical wall in a dungeon.
DC 25: A rough surface, such as a natural rock wall or a brick wall
**Giant spiders get a bonus of +16 to climb, meaning that when they take 10 they get 26.