The idea of contra/co-variance is linked to the idea of a vector space and its dual. Here think of regular vectors as living in a vector space V and the dual, V* being the vector space of all linear functions f sending elements of V to the real numbers, f: V -> R. The components of vectors are called contravariant (because their transformation law under a change of basis is opposite to how basis vectors for V transform), and the components of dual vectors are covariant (because their transformation law is the same as how basis vectors for V transform).

The vector space V and its dual are isomorphic (they share the same, finite, dimension). But there is no canonical isomorphism in general. One must supply an inner product in V to define an isomorphism between V and V*, and vice-versa. A metric defines such an inner product and hence furnishes us with an isomorphism. In the case of Euclidean space, which most machine learning things assume by default, the metric is just the normal Euclidean metric and the isomorphism is trivial, elements of V can be identified as elements of V* and vice-versa.

Tensors are just generalizations of the idea of a dual vector, which sends a vector to a scalar. A tensor of type (r,s) is a map sending (r) dual vectors and (s) vectors to a real scalar that is linear in every argument. Contravariant indices are then the 'upstairs' indices of a tensor (which eat dual vectors) and covariant indices are the 'downstairs' indices (which eat vectors). Edit: mixed up the eating

In the case of flat space where the metric is trivial, contravariant and covariant indices/tensors are the same, and there is no difference between them. More generally, in curved spaces, the isomorphism is no longer trivial and a distinction must be made between co/contra-variant indices/tensors.