Structures that demonstrate nonclassicality are of foundational interest in quantum mechanics, and can also be seen as resources for numerous applications in quantum information processing - particularly in the Hilbert space of N qubits. The theory of entanglement, quantum contextuality, and quantum nonlocality within the N-qubit Pauli group is further developed in this thesis. The Strong Kochen-Specker theorem and the structures that prove it are introduced and explored in detail. The pattern of connections between structures that show entanglement, contextuality, and nonlocality is explained. Computational search algorithms and related tools were developed and used to perform complete searches for minimal nonclassical structures within the N-qubit Pauli group up to values of N limited by our computational resources. Our results are surveyed and prescriptions are given for using the elementary nonclassical structures we have found to construct more complex types of such structures. Families of nonclassical structures are presented for all values of N, including the most compact family of projector-based parity proofs of the Kochen-Specker theorem yet discovered in all dimensions of the form 2N, where N>=2. The applications of our results and their connection with other work is also discussed.