Orbit enumerations represent an important class of mathematical algorithms which is widely used in computational discrete mathematics. In this paper, we present a new shared-memory implementation of a generic Orbit skeleton in the GAP computer algebra system [5,6]. By defining a skeleton, we are easily able to capture a wide variety of concrete Orbit enumerations that can exploit the same underlying parallel implementation. We also propose a generic cost model for predicting the speedups that our Orbit skeleton will deliver for a given application on a given parallel system. We demonstrate the scalability of our implementation on a 64-core shared-memory machine. Our results show that we are able to obtain good speedups over sequential GAP programs (up to 36 on 64 cores).