In this paper, we study user selection (US) strategies for a multiple-input-multiple-output (MIMO) cognitive radio (CR) downlink network, where the r-antenna underlay CR secondary users (SUs) coexist with a primary user (PU), and all terminals are equipped with multiple antennas. Two main scenarios are considered: 1) The t-antenna cognitive base station (CBS) has perfect or partial channel state information at the transmitter (CSIT) from the CBS to the PU receiver (RX), and 2) the CBS has absolutely no PU CSIT. For these scenarios, we propose and evaluate multiple SU selection schemes that are applicable to both best-effort PU interference mitigation and hard interference temperature (IT) constraints. The computational complexity of the proposed schemes can be significantly smaller than that of an exhaustive search with negligible performance degradation. For the selection of C SUs out of K candidates, our proposed sliding window scheme, for example, is of complexity O(K rt(2)), whereas an exhaustive search is on the order of O((GRAPHICS)C(4)r(3)). When t and r are of the same order, the computational complexity of the proposed scheme can be (GRAPHICS)C-4/K times smaller. Mathematical complexity analysis and numerical simulations are provided to show the advantage of our schemes.