Oxygen is paramagnetic because its ground state is a triplet, meaning 2 unpaired electrons (a diradical). The Lewis structure that is typically drawn in introductory Chemistry classes where there is a double bond between the Oxygen atoms is actually the singlet state which is less stable than the triplet state. There are labs which are working on ways of generating singlet Oxygen in an attempt to sterilize solutions or equipment etc.
For the full explanation you need to understand Molecular Orbital Theory.