A natural (iso)morphism is one that is "canonical", or defined without making "choices", or that is defined "in the same way" for all objects.
This is a heuristic I found in every introductory text on category theory I can remember reading (and usually followed with the single/double dual of a vector space as an example) and it took me quite a while to realize that this is not only inaccurate, but just plainly wrong.
Explanation of "wrongness": A natural morphism is a morphism between two functors. That is, a morphism in the category of functors between two categories. And as such, should be thought as usual as mapping the "data" in a way that preserves the "structure" and choices have really nothing to do with it.
For example, thinking of a group $G$ as a one object category, functors from it to the category of sets form the category of $G$-sets. A morphism of $G$-sets is a map of sets preserving the action of $G$ and not a map of sets that "does not involve choices". Same goes for other familiar categories of functors (representations, sheaves etc.)
Another example is the category of functors from the one object category $G$ again to itself. To give a natural map (isomorphism) from the identity functor of $G$ to itself is just to pick an element of the center of $G$. I don't imagine anyone describing it as doing something that "doesn't involve choices".
Moreover, every category $C$ is the category of functors from the terminal one-object-one-morphism category to $C$. Hence, every morphism in any category is a "natural morphism between functors" so there is really no point in specifying a heuristic for when a morphism is "natural". This is utterly meaningless.
In the other direction, it is easy to write down "canonical" object-wise maps between two functors that fail to be natural in the technical sense. Conisder the category of infinite well ordered sets with weakly monotone functions. The "successor function" is definitely defined "in the same way" for all objects, but is not a natural endomorphism of the identity functor in the technical sense.
Explanation of harmfulness": Well I guess it is clear that a completely wrong heuristic is a bad one, but I'll just point out one specific example that is perhaps not so important, but shows clearly the problem. When showing that every category is equivalent to a skeletal category there is a very "non-canonical" construction of the natural isomorphisms. I saw several people get seriously confused about this.
Some thought: One might argue that this heuristic was advanced by the very people who invented category theory (like Maclane) and thus, it is perhaps a bit presumptuous to declare it as "plainly wrong". My guess is that at the time people where considering mainly large categories (like all sets, all spaces, all groups etc.) as both domain and codomain of functors and were focusing on natural isomorphisms. In such situations it is unlikely that the functor will have non trivial automorphisms (or have very few and "uninteresting" ones) and therefore a natural isomorphism will be in fact unique so maybe this is the origin of the heuristic (It is just a guess, I am not an expert on the history of category theory).
This relates to the point that by definition, if specifying an object does not involve choices, then it is unique (this is a tautology). So when we say that an isomorphism is "canonical" we usually mean that given enough restrictions, it is unique (and not just natural in the technical sense). For example, the reason we identify the set $A\times (B \times C)$ with the set $(A\times B)\times C$ is not because there is a natural isomorphism between them, but because if we consider the product sets with the projections to $A,B$ and $C$, then there is a unique isomorphism between them. And this is in line with the general philosophy of identifying objects when (and only when) they are isomorphic in a unique way. In contrast, we don't identify two elements of a group $G$, just because they are conjugate (This is "naturally isomorphic" viewed as functors of one object categories $\mathbb{Z}\to G$) precisely because this natural isomorphism is not unique.
Well, I did not intend this to get so lengthy... I was just anticipating some "hostile" responses defending this heuristic, so I tried to be as convincing as possible!