When in the walking sense, use both interchangeably. Andar means to walk too, but its meaning has gained a broader sense, think of it as "go" or "come", as in "Anda cá", "Come here". I believe you may say "How are you going?" instead of "How are you?", right? The same happens in Portuguese: "Como andas?" (or "como vais?".)

Good question. I would say "caminhar" is a more specific verb, more closely associated with "to walk". "andar" can also mean "to walk" as a synonym of "caminhar" but can have other meanings too. For example, "ele anda triste ultimamente" translates to "he has been sad lately".

Here is a good discussion on this topic: http://forum.wordreference.com/showthread.php?t=2218003