A partial order or poset P=(X, <) on a (finite) base set X determines the set L(P) of linear extensions of P. The problem of computing, for a poset P, the cardinality of L(P) is #P-complete. A set {P₁,P₂,^...,P_k} of posets on X covers the set of linear orders that is the union of the L(P_i). Given linear orders L₁,L₂,^...,L_m on X, the Poset Cover problem is to determine the smallest number of posets that cover {L₁,L₂,^...,L_m}. Here, we show that the decision version of this problem is NP-complete. On the positive side, we explore the use of cover relations for finding posets that cover a set of linear orders and present a polynomial-time algorithm to find a partial poset cover.