How are HOGs calculated?
First, let's talk about what a histogram of directions is.  You can think of the image as a 2D discrete function of x and y: I(x,y). You can take partial derivatives of this function: Ix and Iy. So at each pixel you have the gradient, which is the vector (Ix(x,y), Iy(x,y)). If you compute the magnitude of the gradient, and look at it as an image, you will see the edge map. If you compute the orientation of the gradient at each pixel, you get the edge orientation at that pixel. This is what you take a histogram of.

You divide the range of orientations into some number of bins (let's say 8). Then you look at a single cell. Inside the cell you compute the gradient of every pixel, take its orientation, and add it to the appropriate histogram bin. You can also weigh the contributions by the gradient magnitude, so that pixels with stronger edges contribute more to the histogram.  Once you are done, the histogram encodes the distribution of edge orientations within the cell. Dividing the image into cells preserves some of the spatial layout of the edges.

The size of the cell is a parameter, which you can tune. Typically, it is set to 8x8. If the cell is too small, then you do not have enough pixels for a meaningful histogram. If the cell is too large, then you lose too much of the spatial information.