This is a great question. I think my main tips would be:
1) PLANNING!!!!! Know what your walk will look like before you sit down in front of the computer. Trust me, and save yourself a major headache. Sometimes it can work to create a bland walk cycle and then play with layering things on top of it until you get what you want, but that will always take longer than doing your planning ahead of time.
2) Research! Fire up some movies, observe your family, watch people at the park - whatever it is, study a lot of people walking, and note the differences, and more importantly, how those differences seem to create personality.
3) Study what differences in a walk are caused by body type vs. emotion or personality, and/or how those may be intertwined. You might observe that heavier people have a slightly wider stance, giving their walk a bit more of a rocking motion in the upper body. Does this create personality? I don't know - depends on the character, and what else you may add to the walk, but before you do it, you should know if you're doing it because of their body type or because of their personality. In my opinion, you should get the physics right first, and then layer the personality on top of that, but again - those decisions need to be made before sitting down at the computer.
4) Exaggerate the "personality" aspects of the walk more than the "physical" aspects of it. In other words, if the body mechanics still feel correct for the style you are working in, then that will give your personality decisions a chance to really be showcased. If the body mechanics are wrong, no one will appreciate the decisions you've made about what personality or emotional traits to build into the walk.
Hope that helps!