What exactly is a dimension? How do you exactly define what is and isn't a dimension? I heard somewhere that it is "anything you can move through" but if that is right, why wasn't time and space considered a dimension before Einstein?
 A: I think this depends a lot on what you are doing and how you look at whatever you are looking at.
Speaking of which, how many dimensions does the content displayed by your computer monitor have?
Two, I guess, could be one answer. It's not three dimensional and it certainly is not one strip of pixels.
Let me quote from Carl's great answer that I like to apply to this example:

you cannot get to one property by applying scalar operations on another

Well, no matter what you do to the brightness of one pixel, it will not change the brightness of any other pixel (given you don't blow up your monitor). That means that every pixel can independently be modified and is thus one dimension of the whole. You could say that every digital image that is composed of N pixels has N dimensions. (Yes, that'd mean your smart phone is a device that captures multi million dimensional images. Not sure why no marketing team exploited that fact yet)
This way of thinking about an image is more common in signal processing, computer vision, statistics and/or machine learning.
They even reduce dimensionality, for their algorithms to perform better.

An intuitive way how I'd think about dimensional reduction is statistics.
Look at this scatter plot:

It has two axes, so it's kind of obvious that there are two dimensions, right?
But you could say that this fits quite well to a line:

Now what if the blue line was actually one axis of the plot? I hope you agree that it is at least intuitively plausible that the whole problem "reduces" to one dimension (with some noise of the dots)
[ both images from here ]

This holds true for curves in general.
If you are on a roller-coaster, you will move through the 3 spatial dimensions (if you are not on a very lame roller coaster), but the dimensionality of your movement is (hopefully) only 1, because you want to stay on track.

You can also go the other way round. A Hilbert Curve is a curve, that fills a two dimensional space. the article states:

its Hausdorff dimension is 2 (precisely, its image is the unit square, whose dimension is 2 in any definition of dimension

You should think about this tomorrow, when you mow your lawn. One usually always goes forward/backwards, with angled turns, but never sideways. Just like on the roller-coaster. But now you actually did move twodimensionally. 

And then there are fractals with fractional dimensions, which I only want to mention here.

conclusion (or rather lack thereof)
The content of your monitor can be considered to have a variety of dimensions, depending on what you are interested in.
A: Coming from a math perspective,  I would define a dimension as "any property which is orthogonal to all other properties."   "Orthogonal" here means you cannot get to one property by applying scalar operations on another.  For example,  the x-axis dimension can never become a y-axis value, and similarly for time vs.  spatial dimensions.
For that matter, it's fair to consider any "unit" as a dimension, since you can't apply any function to convert, say,  mass or color of an object into one of its spatial dimensions.
A: In a geometrical context, the dimension (at a point) roughly speaking is the number of coordinates you need to identify any point in a fixed neighbourhood. Note that in a geometrical context, the least you need is a topology, in order to be able to speak of continuity, neigbourhoods, etc. 
This intuitive definition used to work quite well, but at a certain point space filling curves were discovered, and people started wondering if it could be that $\Bbb R^n$ and $\Bbb R^m$ might be homeomorphic (i.e. topologically equivalent) for some $n\ne m$. The proof that they are not is surprisingly hard, and uses algebraic topology. 
This gives a good definition for spaces that locally look like $\Bbb R^n$ or $\Bbb C^n$, like manifolds, simplicial complexes, etc. 
In different contexts, like in algebraic geometry, there are different definitions (like the length + 1 of the longest chain of irreducible subvarieties: point $\subset$ curve $\subset\cdots\subset$ hypersurface $\subset$ irreducible component of the whole space), all with their own subtleties: it is often surprisingly hard to find a good definition of dimension and prove that it behaves as it should (with the exception of vector spaces).
A: In this context, I usually explain it (non-mathematically) by saying that the number of dimensions is the number of values you need to specify where an event occurs. For most people this involves space and time (but for particle physicists it might involve more values ;).
Anyway, certainly even people before Einstein would need to specify the time as well as the spatial location of an event (3 dimensions, X/Y/Z or lat/long/height etc), giving 4 dimensions.
What Einstein (and really others before like Minkowski) added was the important extra piece of physics that not only are the 3 ordinary spatial dimensions interchangeable, but the 4 dimensions X,Y,Z and T are too, to some extent.
Consider a 1 meter long ruler which is laid out from a corner in a room along one wall - you can consider the distance along that wall to be dimension X. Then you rotate the ruler so it lies along the other wall, dimension Y. Then you rotate it upwards, so it's along the wall up to the ceiling, dimension Z.
This shows that at least the 3 spatial dimensions belong together; you can take an object and rotate it around these dimensions, or in other words, take some value from one dimension to give it to another.
Einstein extended this reasoning to involve time as well as a "rotateable" part of physical objects and events. It's not a completely accurate analogy as you will know if you study the mathematics of special relativity, but it's in the ballpark.
A: Our rigorous definition of "dimension" comes from linear algebra. This is going to be a quick run-through of the mathematical way of describing dimensions, and then its physical significance. 
The first concept needed is a vector space. A vector space can effectively be thought of as a collection of points that satisfy a few particular (and very useful) properties. The important physical note here is that all of classical and relativistic physics treats the space we live in as a vector space. 
All vector spaces have at least one basis. A basis is a set of (linearly independent) vectors with a few properties. The notable one is that any vector in the vector space can be expressed as a scalar multiple of those basis vectors. For instance, in 3D space, we have: $$e_1=(1, 0, 0)\\e_2=(0, 1, 0)\\e_3=(0, 0, 1)$$
Any vector in 3D space can be expressed as a combination of these vectors. For instance, $(5, 3, 7) = 5*(1, 0, 0) + 3*(0, 1, 0) + 7*(0, 0, 1) = 5e_1+3e_2+7e_3$.
The dimension of a vector space is the number of basis vectors needed to completely describe all points in the space. (Because of linear independence, which I won't describe here, this number is fixed for a given vector space.)

The physical significance of this is fairly straightforward. In classical mechanics, there is an implicit assumption that the world can be described as a vector space of dimension 3. In other words, it only takes three linearly independent vectors to describe the entire space in which we live. Relativity threw this out the window. 
Consider two objects A and B positioned at $(1, 1, 1)$ at time 0. I'll write this as $(1, 1, 1, 0)$. Suppose one of them remains stationary from your perspective, and one of them moves around in a large circle once at high velocity. Classically speaking, after this iteration, the objects would have the configuration: $$\begin{align}A &= (1, 1, 1, t)\\B&=(1, 1, 1, t)\\A-B &= (0, 0, 0, 0)\end{align}$$
In other words, classically, there is no difference in the temporal or spatial configurations of A and B. Three dimensions is sufficient to describe this. However, with relativity, we end up with $$\begin{align}A &= (1, 1, 1, t+\Delta t)\\B&=(1, 1, 1, t)\\A-B&=(0, 0, 0, \Delta t)\end{align}$$
As $A$ was moving, there is some temporal difference between $A$ and $B$. Since $A - B = (0, 0, 0, \Delta t)$, a fourth basis vector is mandatory to completely describe the configuration we've just witnessed. Consequently, space must be four-dimensional under relativity.
