Design using composition and interfaces in Java

I'd suggest strategy pattern here. In short:

interface TailedAnimal {
    void moveTail();
}
interface HornedAnimal {
    void hitWithHorn();
}
class Rhinoceros() implements TailedAnimal, HornedAnimal {
    private TailedAnimal tail;  //Instantiate it somehow e.g. constructor, setter
    private HornedAnimal horn;  //Instantiate it somehow e.g. constructor, setter
    public void moveTail() {
        tail.moveTail();
    }
    public void hitWithHorn() {
        horn.hitWithHorn();
    }
}

By using this you encapsulate behavior in a concrete implementation of the interfaces, and may easily share exactly the same behavior for a few animals, as well as change it at run-time.

I think you must avoid setters in general. If you can, use immutable objects, and initialize its private data into its constructor.

To distinguish animals, I used another pattern, the visitor one. It's verbose, but you don't have to test directly what animal you're processing.

public class Animals {
private Animals() {
}

interface Animal {
    void accept(final AnimalProcessor visitor);
}

interface AnimalProcessor {
    void visitTailed(final TailedAnimal tailedAnimal);

    void visitHorned(final HornedAnimal hornedAnimal);
}

interface TailedAnimal extends Animal {
    void moveTail();
}

interface HornedAnimal extends Animal {
    void hitWithHorns();
}

static class Dog implements TailedAnimal {
    public void moveTail() {
        //To change body of implemented methods use File | Settings | File Templates.
    }

    public void accept(final AnimalProcessor visitor) {
        visitor.visitTailed(this);
    }
}

static class Cat implements TailedAnimal {
    public void moveTail() {
        //To change body of implemented methods use File | Settings | File Templates.
    }

    public void accept(final AnimalProcessor visitor) {
        visitor.visitTailed(this);
    }
}

static class Ram implements HornedAnimal {
    public void hitWithHorns() {
        //To change body of implemented methods use File | Settings | File Templates.
    }

    public void accept(final AnimalProcessor visitor) {
        visitor.visitHorned(this);
    }
}

static class Rhinoceros implements HornedAnimal, TailedAnimal {
    public void hitWithHorns() {
        //To change body of implemented methods use File | Settings | File Templates.
    }

    public void moveTail() {
        //To change body of implemented methods use File | Settings | File Templates.
    }

    public void accept(final AnimalProcessor visitor) {
        visitor.visitTailed(this);
        visitor.visitHorned(this);
    }
}

public static void main(String[] args) {
    Collection<Animal> animals = new ArrayList<Animal>(Arrays.asList(new Dog(), new Cat(), new Rhinoceros()));
    for (final Animal animal : animals) {
        animal.accept(new AnimalProcessor() {
            public void visitTailed(final TailedAnimal tailedAnimal) {
                // you do what you want when it's a tailed animal
            }

            public void visitHorned(final HornedAnimal hornedAnimal) {
                // you do what you want when it's a horned animal
            }
        });
    }
}
}