Well, for me, in this context:
Em cima da = on, but meaning on top of
Na [árvore] = on/in the tree (most likely on a branch, but could also mean inside the tree).
I would never say "em cima da árvore" unless I really meant on top of the tree. It'd always be "um gato na árvore".
But looking at Paulenrique's comment, I guess it might be a regional thing o.O