I go the rules route. I don't know that you can learn algebra any other way, can you? I mean, if you don't know the rules, how are you going to do the problem? I hated proofs, though that is more applicable to geometry.
The rest of it is like what BrentRitterbeck says. You just need to do enough problems to be able to look at a problem and say to yourself "I think this technique will work."
Proofs in algebra aren't usually very enlightening with respect to the theorem they are trying to prove, but they can teach you a new technique (e.g. proving the quadratic equation can teach you how to "complete the square").