Caving is the way to go
There's no specific way to find an Abandoned Mineshaft. Caves and Ravines are probably your best bet, because you can see and cover large distances underground in these. Even so, finding one may take quite a lot of exploring.
Using X-Ray Bugnology
If you don't want to go exploring so much, you can try using an X-Ray machine to see underground, but this is technically using bugs. A simple X-Ray Machine consists of two regular Fenceposts and two Redstone Blocks. Dig a 2x1x3, stand in it and close the top with dirt. Place the fenceposts on top of each other, and walk up to them. Then place the Redstone Blocks against the fenceposts, starting at the bottom. You are now in the Redstone Blocks, whose textures aren't rendered from inside, and you can see underground as far as the next cave in all directions. Mineshafts naturally spawn some Torches, so you can identify them easily.
Avoiding Cave Spiders is no problem when you haven't found a Mineshaft yet, since they only spawn from spawners there. In a Mineshaft, there is a high chance to encounter one of these, but if you want to avoid them, look out for large amounts of cobweb. The spawners are typically surrounded by around 5-15 blocks of Cobweb in all directions, which makes them easy to spot, and turn another way. I suggest taking them on though. With decent weapons and armor (iron usually suffices), they are not to hard. Try to take cover behind the fenceposts and cut your way through the cobwebs with a sword (or shears). Drinking a bucket of milk will neutralize the poison.