Coffee is allowed in a primal diet as a "sensible vice"; meaning like dark chocolate, feel free to enjoy in moderation!
Black coffee is essentially a nutritional void, and contains virtually no calories; the only thing you can really knock it for is the caffeine and the associated effects. For this reason it probably doesn't really matter which particular "kind"/brand/roast etc you are drinking so long as it isn't poisonous (although I'm sure someone has an opinion on organic & fair trade). Obviously once you add sugar or milk, it's a different story.
Personally I religiously drink a cup of coffee every day. Nothing I like better than sipping a hot coffee with a little cream in the park at lunch after my salad.