anda vs caminha
When would you use Ele anda as opposed to Ele caminha?
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