Finding an astrometric solution from an image with Astrometry.net is usually called plate solving. As mentioned in the comments, it is based on pattern matching, using a large set of databases that are pre-computed for various field of view and plate (or pixel) scale. The ArXiv paper Astrometry.net: Blind astrometric calibration of arbitrary astronomical images provides some details of how it works. From their abstract ...
After robust source detection is performed in the input image, asterisms (sets of four or five stars) are geometrically hashed and compared to pre-indexed hashes to generate hypotheses about the astrometric calibration. A hypothesis is only accepted as true if it passes a Bayesian decision theory test against a null hypothesis.
The blind solution described in the paper is obtained directly from a photo without any additional input, but even a rough guess for the field of view can provide considerable speedup by narrowing the number of databases to be searched. Additional speedup is possible if the scale (arcsec/pixel), FOV and approximate coordinates in the sky are provided.
Astrometry.net code and databases can also be downloaded and run locally on unix/linux computers, and on Windows using Cygwin. There are several other plate solvers available, often included with, or designed to interface with, software that controls a telescope, mount, camera, etc. for astrophotography.
Edit: Some additional info related to the comments.
In finding a solution, they must deal with imperfections of real images, including defects, optical and atmospheric distortion, etc. along with small positional changes of stars. Roughly speaking, they obtain a solution by using a best fit to several asterisms, each containing a small number of stars.
Noise in the image and distortion caused by the atmosphere and telescope optics lead to noise in the measured positions of stars in the image. In general this noise causes the stars in a quad to move slightly with respect to each other, which yields small changes in the hash code (i.e., position in code space) of the quad. Therefore, we must always match the image hash code with a neighborhood of hash codes in the index.
Also, they are able to ignore defects and moving objects like planets, asteroids, etc. in finding matches.
However, we also know that some fraction of the stars in the query image will have no counterpart in the index, due to occlusions or artifacts in the images, errors in star detection or localization, differences in the spectral bandpass, or because the query image "star" is actually a planet, satellite, comet, or some other non-star, non-galaxy object. True stars can be lost, and false stars can be added. Our foreground model is therefore a mixture of a uniform probability that a star will be found anywhere in the image--a query star that has no counterpart in the index--plus a blob of probability around each star in the index, where the size of the blob is determined by the combined positional variances of the index and query stars.
Their goal was not to achieve high astrometric precision.
There are several automated calibration systems that refine the astrometric calibration of an image to produce a high-precision alignment to a reference catalog given a good first guess (for example, Valdes et al. 1995; Mink 2006; Bertin 2005). These systems are reliable and robust, but they require a reasonable first guess about the image pointing, orientation, and scale. Our system can be used to create that good first guess.