With extreme difficulty. People haven't really known how far away the stars are for very long. The first measurement is generally attributed to Friedrich Wilhelm Bessel, in 1838. He wasn't really the first, but he did a good job of it, and the first success took place right around that time.

The idea is to use geometry to measure the distance. One builds a triangle. For the base of the triangle, use the diameter of the orbit of the Earth around the Sun. It's about 93,000,000 miles to the Sun, so the diameter is twice that, or 186,000,000 miles. Look at a star just before sunrise, and note the precise angle location. Then wait nearly six months, and just after sunset, find that same star and note the precise angle. (Really measure the angle relative to stars near it, which one hopes are much farther away, and so aren't moving so much.) This yields a base length and two angles of a triangle, it's a simple matter to figure out how far it is to the the vertex at the end, where the star is. The phenomenon is called parallax. The difference in the angles measured is referred to as the parallax angle.

However, it turns out, that to a very good approximation, the two angles measured are the same, even for the nearest stars. In fact, the ancients, seeing no parallax, used this as an argument that the Sun goes around the Earth. Obviously, if the Earth isn't moving, there is no parallax, or so went the argument. Really, the ancients couldn't believe that the stars were so far away. And, their estimates for the minimum distances were low.

Not only is the parallax angle so small as to be essentially zero, its worse. The Earth's atmosphere makes it difficult at best to measure angles with enough precision. The atmosphere has different temperatures in spots, and hotter air is less dense than colder air, so light refracts unpredictably as it passes through the layers. If the air is turbulent, one might be able to see details or measure angles no better than about 3 arc seconds. If the air is smooth or still, it might be as good as 0.5 arc seconds. Since there is this sunrise/sunset thing, the atmosphere is generally going to be turbulent. After all, on the sunset side, the Sun was just boiling the air - it's still hot. Can this be good enough?

Proxima Centauri is about 4.22 light-years from the Sun. It is the nearest star whose distance has been measured. The parallax angle is about 0.772 arc seconds. So there must be nights of excellent seeing, with the best equipment and one must diligent in order to get data good enough to be able to compute a distance that makes any sense. When the measurement is repeated, the answers have to agree.

Proxima Centauri is the closest star, but it wasn't discovered until 1915. It's a red dwarf type star. It isn't very bright. It is about as dim as a star can be and still be a star. One would expect that the bright stars would be the nearby ones, due to the inverse square law of light. That is, if there are two flashlights that are the same brightness at the same distance, and one is moved twice as far away, it will appear four times dimmer.

It was not yet known that the brightest stars in the sky can be intrinsically 10,000 times brighter than the sun. Further, there are stars that are a good deal dimmer than the sun. So, a star that is 100 times farther away than the nearest stars can be as bright. This is indeed the case. Some of the brightest stars in the sky have still eluded direct parallax distance measurement. Even from space based observations, where there is no atmospheric distortion. In any case, people attempting to measure stellar distances often unwittingly looked at very distant objects.

Bessel had previously performed work reducing other astronomers star position observations. He published the positions of 3,222 stars, taking into account errors in the instruments, angle through the atmosphere, etc. This was really a first class data reduction publication. The data spanned a hundred years, with at least some stars measured early and late. Bessel computed the proper motions of 38 stars. Proper motion is the angular motion a star has compared with the background stars. Such proper motion will continue in the same direction at the same speed for years. Stars with high proper angular motions are either moving faster, or are quite close, and so make good candidates for parallax studies. The average proper motion then must be accounted for from the 6 month parallax angles. This requires a few more observations, and some math.

So, Bessel determined the parallax to 61 Cygni to be 0.314 arc seconds in 1838. How? That is, 0.314 arc seconds is less than the 0.5 arc seconds that the atmosphere allows. Well, it turns out that when looking at a star, the star is unresolved. That is, one doesn't see a disk, like the moon or most of the planets. What one sees is a dot. This dot can be considered to be infinitely tiny. And, this dot moves around the field of view erratically. What can be done is put a knife edge across the field of view, and sweep past the star. Watching carefully, one sees the star bounce back and forth across the edge. Then using the timing as the star crosses the edge, one can improve data accuracy. Eventually one gets an idea of where the center of bouncing is. Perform the measurement many times, and average the positions. The more measurements made, the better the result. If one works hard, one can do better, and there is no theoretical limit. There are only practical limits.

The currently accepted value of the parallax of 61 Cygni is 0.292 arc seconds. So Bessel was within about 7% of the answer. This was a big leap forward. This nearby star is about 11 light years away. This is a much larger distance than people had dealt with before. Even if he was a factor of two off, he'd have introduced something profound to the study of the Universe. It's an Astronomical Distance. Together with Geological Time, understanding of these concepts allows for developing a basic framework for considering the physical Universe.

Perhaps you thought you first go to Home Depot, and get a really long tape measure.