What exactly is magnetic flux? It is intuitive to think of an electric field, which describes the variance in the force acting on a charged particle if it were located in a certain position. However it is not so easy to understand what magnetism is and what flux is.
Apparently magnetism is an effect of special relativity for moving charges, but this is also hard to understand.
What is magnetic flux?
 A: 
It is intuitive to think of an electric field, which describes the variance in the force acting on a charged particle if it were located in a certain position

The electric field $\mathbf E$ is actually just a force per unit charge $(q\mathbf E=\mathbf F)$, where $q$ is the charge the electric force is acting on. It does not describe a variance of a force.

However it is not so easy to understand what magnetism is and what flux is. Apparently magnetism is an effect of special relativity for moving charges, but this is also hard to understand. What is magnetic flux?

So it is true that electric and magnetic fields can be viewed as parts of the same thing in SR, but this view is not needed to understand magnetic flux. Similar to our above discussion about $\mathbf E$, the magnetic field $\mathbf B$ can also be described by the force it exerts on a charged particle moving with velocity $\mathbf v$. 
$$\mathbf F=q\mathbf{v}\times\mathbf{B}$$
A good way most introductory physics classes explain the direction of the magnetic field is that it points in the direction a compass would point. Of course, we can determine the entire (magnitude and direction) magnetic field from its current sources using the Biot-Savart law in the same way we can determine the electric field from its charge sources using Coulomb's law, but this is not the crux of your question.
Magnetic flux is a specific case of the more general idea of the flux of a vector field $\mathbf V$, whose origin comes from fluid dynamics. The flux $\Phi$ of a vector field across some surface is given by the surface integral
$$\Phi=\int \mathbf V\cdot\text{d}\mathbf A$$
Where $\text{d}\mathbf A$ is an infinitesimal area element vector whose direction is normal to the surface.
This can be applied to the magnetic field, where then you would just replace $\mathbf V$ with $\mathbf B$. Flux tells you "how much field is flowing through the surface". Since the integral depends on the dot product $\mathbf V\cdot\text{d}\mathbf A$, you can see that if the field is normal to the surface then we get maximum flux (maximum flow), but if the field is parallel to the surface we get no flux (no flow).
