What is a covariant functor?

A covariant functor is just the normal Functor class:

class Functor f where
    fmap :: (a -> b) -> f a -> f b

For instance, Maybe (as you noted):

instance Functor Maybe where
    fmap _ Nothing = Nothing
    fmap f (Just a) = Just (f a)

However, there is another type of functor: contravariant functors. These are defined as follows:

class Contravariant f where
    contramap :: (a -> b) -> f b -> f a

Note that compared to fmap, contramap has reversed the order of b and a:

fmap      ::       Functor f => (a -> b) -> f a -> f b
contramap :: Contravariant f => (a -> b) -> f b -> f a
                                         --   ^      ^
                                         --   look!

Now, does this crazy Contravariant class even have any instances? Well, yes. For example, here's the definition of a Predicate:

newtype Predicate x = Predicate { decide :: x -> Bool }

In other words, a Predicate x is a function which calculates a condition on an x. We can specialise contramap to Predicates:

contramap :: (a -> b) -> Predicate b -> Predicate a

Which is equivalent to:

contramap :: (a -> b) -> (b -> Bool) -> (a -> Bool)

Basically, given a Predicate on bs, and a mapping from as to bs, you can contramap to get a Predicate on as. (I'll leave the implementation as an exercise.) Here's an example (untested):

hasMultChars :: Predicate String
hasMultChars = Predicate $ \x -> length x > 1

showInt :: Int -> String
showInt = show

intHasMultChars :: Predicate Int
intHasMultChars = contramap showInt hasMultChars

As it turns out, contravariant functors are a lot less common - and so a lot less useful - than normal covariant functors. So in practise, we leave out the 'covariant', since it doesn't add anything in most cases.

A covariant functor is one where the “inside” and “outside” arrows point in the same direction.

class Functor f where
  fmap :: (a -> b) -> (f a -> f b)

A contravariant functor is one where the “inside” and “outside” arrows point in opposite directions.

class Contravariant f where
  contramap :: (a -> b) -> (f a <- f b)

...or, with proper Haskell syntax,

  contramap :: (a -> b) -> (f b -> f a)

That's generally an indication that the parameter-type occurs somewhere as a function-argument in the data type, like

data DepInt x = DepInt (x -> Int)

instance Contravariant DepInt where
  contramap f (DepInt g) = DepInt $ g . f

Conversely, if the argument only appears as-is or to the right of a function arrow, then it is a covariant functor. This is the case for most functors, which is why the class is simply called Functor.