Why is the cross product of two vectors orthogonal? What is the intuition behind the fact that the cross product of two vectors is orthogonal? Every video I've seen just says it is orthogonal but they do not explain why. Since I have terrible memory, I need to understand things intuitively or I will just forget them.

By the way, I do not understand the intuition behind the calculation for the cross product either, so if that is necessary to understand why it is orthogonal, please explain.
Its not really an "intuition" thing, the cross product is defined that way. The following may help you understand why.

The short answer is that the cross product appears in many physical systems - most famously in calculating the force produced by an electrical current in a magnetic field. But this begs the question of why it appears so often in physics.

In physics, you often get linear relationships - in the example above doubling the current will double the force, as will doubling the magnetic field. So the current vector and magnetic vector are somehow multiplied together to find the force vector. You could potentially define vector multiplication in lots of ways. But there is an additional constraint in physics, that you must get the same answer for the force vector however you orient your co-ordinate system. Nature doesn't have a coordinate system, so the answer must be the same however you define what is the "x axis" and what is the "y axis". If you set up a coordinate system with the x axis along the direction of the magnetic field and the y axis along the current vector, then you should get the same answer for force as if you set up the co-ordinate system with x axis in the current direction and the y axis along the magnetic field direction.

All physical laws must follow this rule; nature doesn't have a preferred direction for x and y. The dot product (which presumably you have just learned about) follows this rule.

If you want to multiply two vectors in 3D space to form another vector, up to a constant term the only definition of vector  multiplication which has this property of being independent of the coordinate system is the cross product. It is the unique definition of vector multiplication which is independent of the choice of coordinate system.

So nature follows this rule whenever two (3D) vectors are multiplied together to form a 3rd vector. Any other rule would be depend on the choice of coordinate system. So natural processes in three dimensions are in a sense forced to use this rule, because its the only rule which is independent of the co-ordinate system. In 2D, there is no possible rule which is independent of the co-ordinate system. In higher dimensions there are more choices. But we live in a 3D Universe (spatial dimensions), so the cross product rule is forced onto nature and hence onto physics and maths.
The cross-product was defined by Gibbs to mimic the properties of quaternion multiplication without the negativity of the square.
Quaternions are very economic way to represent rotations in 3D and therefore many physical equations. 

See for example here.

http://en.wikipedia.org/wiki/Geometric_algebra

http://en.wikipedia.org/wiki/History_of_quaternions

http://fexpr.blogspot.be/2014/03/the-great-vectors-versus-quaternions.html