How do convolution matrices work?

How do those matrices work? Do I need to multiple every single pixel? How about the upperleft, upperright, bottomleft and bottomleft pixels where there's no surrounding pixel? And does the matrix work from left to right and from up to bottom or from up to bottom first and then left to right?

Why does this kernel (Edge enhance) : http://i.stack.imgur.com/d755G.png turns into this image: http://i.stack.imgur.com/NRdkK.jpg

You might want to read this tutorial, but I'll also try to answer below.

How do 2D convolutions work?

I find it useful to think of 2D convolutions as image filters, as you have. The idea is that you use the filter to take an old grid of values, the numerical representations of colors, and turn it into a new grid. This is done by laying the filter on top of the old grid, multiplying the numbers in the filter with the numbers in the grid, summing them, and putting them into the new grid at the center of the filter. More formally, for a $2n+1$ by $2m+1$ filter $F$: $$A'_{x,y} = \sum_{i=-n}^n ~ \sum_{j=-m}^m (F_{i,j}) (A_{x+i,y+j})$$ For example, a 3x3 edge-highlighting filter: $$\text{Old} = \begin{bmatrix} 0 & 1 & 2 & 1 & 0 \\ 1 & 2 & 3 & 2 & 1 \\ 2 & 3 & 4 & 3 & 2 \\ 1 & 2 & 3 & 2 & 1 \\ 0 & 1 & 2 & 1 & 0 \end{bmatrix}, \text{Filter} = \begin{bmatrix} 0 & -1 & 0 \\ -1 & 5 & -1 \\ 0 & -1 & 0 \end{bmatrix} \quad \rightarrow \text{New} = \begin{bmatrix} ? & ? & ? & ? & ? \\ ? & 2 & 5 & 2 & ? \\ ? & 5 & 8 & 5 & ? \\ ? & 2 & 5 & 2 & ? \\ ? & ? & ? & ? & ? \end{bmatrix}$$

Do I need to multiple every single pixel?

You always want to apply the filter to the entire inside of the grid. In order to do the borders, you need some sort of boundary condition. Common boundary conditions are cyclic, the bottom connects to the top and the left to the right; mirror, add an extra row above that is the same as the top row, below that is the same as the bottom row, etc; or constant, where the border is some fixed pattern, often zero. For images, the border is generally really small compared to the inside, so you probably don't care if you just neglect it.

Does the matrix work from left to right and from up to bottom or from up to bottom first and then left to right?

The filter should always be applied to the old grid, which doesn't change. Therefore, it doesn't matter in what order you apply it; you can start from whichever pixel you'd like and go in any direction. This is good, because it makes the task embarrassingly parallel.

Why does edge enhance work?

The filter: $$F = \begin{bmatrix} 0 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix}$$ picks out vertical edges. It is easiest to see its action on a line: $$\begin{bmatrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{bmatrix} \quad \longrightarrow_F \begin{bmatrix} ? & 0 & 1 & -1 & 0 \\ ? & 0 & 1 & -1 & 0 \\ ? & 0 & 1 & -1 & 0 \\ ? & 0 & 1 & -1 & 0 \\ ? & 0 & 1 & -1 & 0 \end{bmatrix}$$ It is actually computing a directional derivative, $\partial/\partial x$, which picks out slopes along horizontal lines, such as vertical edges.