I suggest to you to thoroughly study a really insightful tutorial about Support Vector Machines for Pattern Recognition due to C. Burges. It isn't elementary, but it gives significant information about SV learning. It really helped me as a beginner!
Concerning your first question. $\mathcal{H}\colon\mathbf{w}\cdot\mathcal{x}+b=0$ describes the locus of points belonging to hyperplane $\mathcal{H}$. $\mathbf{x}$ denotes an arbitrary vector in your input space, that is, the space where your training samples (i.e. $\mathbf{x}_i$, $i=1,\ldots,l$) live. Often this is some subset of $\mathbb{R}^n$.
As for your second question, granted that you have learned some separating hyperplane, $\mathcal{H}\colon\mathbf{w}\cdot\mathcal{x}+b=0$ (and this is exactly what a linear SVM does), then given some unseen (that is, a new, without truth label) datum $\mathbf{x}_t$, you have to classify it to some class, by giving it a truth label $y_t\in\{\pm1\}$. The way you do so is by checking the sign of the decision function $f(\mathbf{x})=\mathbf{w}\cdot\mathcal{x}+b$, that is, $y_t=\operatorname{sgn}(f(\mathbf{x}_t))$. $\operatorname{sgn}(f(\mathbf{x}_t))>0$ means that your datum is "above" the separating hyperplane and thus has to be classified as positive, while $\operatorname{sgn}(f(\mathbf{x}_t))<0$ means that your datum is "under" the separating hyperplane and thus has to be classified as negative. If $\operatorname{sgn}(f(\mathbf{x}_t))=0$ it means that you testing sample belongs to the separating hyperplane, and thus there cannot be some decision about its truth label.
Note that if $-1<f(\mathbf{x}_t)<+1$ then the testing datum lies inside the so-called margin of the classifier (take a look at the tutorial above for more information).
EDIT
I would like to add some comments below motivated by the discussion between @Pegah and me in the comments.
I guess because in other contexts the vectors $\mathbf{x}$ in the
equation for hyperplanes refer to the points on the hyperplane, but
here $\mathbf{x}$ refer to input vectors which are not necessarily on
it, which seemed ambiguous to me.
This is not correct, actually. $\mathbf{x}\in\mathbb{R}^n$ refers to any point in the Euclidean $n$-dimensional space. Now, if and only if such a point belongs to the hyperplane $\mathcal{H}$, it satisfies the equation $\mathbf{w}\cdot\mathcal{x}+b=0$. In other words, the hyperplane $\mathcal{H}$ is the locus of the $n$-dimensional points that satisfy $\mathbf{w}\cdot\mathcal{x}+b=0$. For all other point it must hold that $\mathbf{w}\cdot\mathcal{x}+b>0$ or $\mathbf{w}\cdot\mathcal{x}+b<0$.
I have another question though if you don't mind: I do understand that
we can label new input vectors with $-1$ and $+1$, but why (as in the
script linked by you) do we assume that
$\mathbf{w}\cdot\mathcal{x}+b\leq-1$ and
$\mathbf{w}\cdot\mathcal{x}+b\geq+1$ respectively? I don't see that
explained anywhere, and am wondering why it could not be a and $-a$
for some $a\in\mathbb{R}$. Is it simply scaling (and are hence both
sides of the inequality scaled, i.e. divided by $a$?).
The above inequalities are our constraints to state that the training data are linearly separable, which -of course- is a very strict and coarse assumption. This leads to the so-called hard-margin SVM, which is in the form of the hyperplane $\mathcal{H}$. Keep in mind that you will never achieve to get such a hyperplane if your training data are not linearly-sparable, since the objective function of the hard-margin SVM (i.e. the dual Lagrangian) will grow arbitrarily large. Then, you need to relax these constraints by introducing the slack variables $\xi_i$ which permit the training data to be non-linearly separable. the reason why there are $+1$, $-1$'s here is the indeed there is a normalization by the norm of $\mathbf{w}$.
Concerning your two additional questions:
(1) You have added that a slack variable might be introduced for
non-linearly separable data - how do we know that the data is not
linearly separable, as far as I understand the mapping via kernel has
as a purpose to map the data into a vector space where in the optimal
case it would be linearly separable (and why not using a non-linear
discriminant function altogether instead of introducing a slack
variable?)
First of all, you do not know a-priori that your data are linearly separable (in your input space). It is reasonable, though, that you want to solve the problem in both cases. We introduce the slack variables such that a training sample may enter the wrong class, contributing this way to the total loss. What we desire is to minimize this total loss. To be more specific, let $\xi_i\geq0$ be the aforementioned slack variables. When $0\leq\xi_i<1$, then the sample lies on the margin, but it is not yet misclassified. If $\xi_i=1$ then the sample lies on the contour (still not misclassified). However, if $\xi_i>1$, then the sample lies on the wrong class. In all the above cases (i.e., whenever holds that $\xi_i>0$) there is an error which must be measured (and minimized!). We measure the total error by summing up all the $\xi$'s distances, that is, $C\sum_{i}\xi_i$. $C$ is a user-specified positive parameter (a larger $C$ corresponding to assigning a higher penalty to errors).
Now, what about the kernels? We use a kernel because we know that by going to the feature space (i.e., the space where the kernel maps our input space) it is very likely that our data becomes linearly separable. Then we employ our linear method to classify them (linearly!). What is linear in the feature space is not linear in the original input space (granted that the selected kernel is not the linear kernel $k(\mathbf{x},\mathbf{x}')=\mathbf{x}\cdot\mathbf{x}'$). When we go back to the input space, the decision function we have found in the feature space is not linear.
(2) I've seen that for the optimization only one of the inequalities
$w*x = b \geqslant 1$ is being used as a linear constrained - why?
This could not be true... The constraints are still $y_i(\mathbf{w}\cdot\mathbf{x}_i+b)+\xi_i\geq1$, $\forall i$
Best Answer
A dichotomy, in this context, is a way to label the all of points with two labels, say red and blue. Two dichotomies are distinct if at least one point is labeled differently. There are $2^P$ dichotomies for $P$ points. However, we say a dichotomy is realized by a hyperplane if there is a hyperplane so the red points are on one side and the blue points are on the other. Cover's counting theorem tells you the number of these dichotomies which are realized by hyperplanes.
Once you have proved the formula $C(P,N)=2\sum_{k=0}^{N-1}\binom{P-1}{k}$, it easily follows* from properties of the binomial coefficients that...
$C(P,N)=2^P$ whenever $P\le N$. This means that every dichotomy can be realized by a hyperplane when $P\le N$, i.e. when there aren't too many data points.
$C(P,N)<2^P$ whenever $P>N$. This means that when there are too many data points, then there will exist some dichotomies that are not realized by hyperplanes. Therefore, if $P>N$, and you are trying to solve a classification problem using a hyperplane, there is a possibility you will not be able to succeed.
Finally, consider the ratio $$ \frac{C(P,N)}{2^P}=\frac{\text{# dichotomies realized by hyperplanes}}{\text{total # of dichotomies}} $$ This is always between $0$ and $1$. The closer to $1$ it is, the more likely a random dichotomy is to be one of the ones realizable by a hyperplane. This is the $y$-axis of the graph. Cover's theorem implies that as $P$ remains fixed, and $N$ increases, then the above ratio increases or stays the same. This is what is meant by the statement "In higher dimensions, a dichotomy is more likely to be realized by a hyperplane."
* Let me prove these two facts. First, suppose $N=P$. In this case, $\sum_{k=0}^{N-1}\binom{P-1}{k}$ is simply the sum of all binomial coefficients in row number $P-1$ of Pascal's triangle, which is well known to be $2^{P-1}$. This can be proven with the binomial theorem: $$ 2^{P-1}=(1+1)^{P-1}=\sum_{k=0}^{P-1}\binom{P-1}k 1^{k}1^{n-k}=\sum_{k=0}^{P-1}\binom{P-1}k $$ Multiplying by $2$, you get $C(P,N)=2\cdot 2^{P-1}=2^P$.
If instead $N<P$, then the sum $\sum_{k=0}^{N-1}\binom{P-1}{k}$ only extends up to $k=N$, so it misses some of the binomial coefficients in row $P-1$. Therefore, the sum must be less than $P$. Finally, if $P>N$, then the sum extends past $P-1$, containing coefficients like $\binom{P-1}{P},\binom{P-1}{P+1}$, etc. These are all zero, by definition, so the sum is still $2^{P-1}$ in this case.
When $N=5,P=30$, $$ \frac{C(P,N)}{2^P}=\frac{2\sum_{k=0}^{5-1}\binom{30-1}{k}}{2^{30}}=\frac{\binom{29}0+\binom{29}1+\binom{29}2+\binom{29}3+\binom{29}4}{2^{30}}\approx 0.5\times 10^{-5} $$