Question

How do I get fossils in black?

Answer 1

The Cover and Plume Fossils can be obtained from a Backpacker at Relic Castle. You may choose one of the two Fossils, and the other will be kept by the Backpacker.

The other Fossils from Gen 1 to 4 can be obtained from a Worker at Twist Mountain, who will give you a random one daily.

Source: Experience

Answer 2

You know where you evolve glaceon? West of that icy rock, there's a door you can walk through. Through that, there's a worker looking at a wall. Talking to him will give you a random fossil daily. None of them will be unova.