The Sun piece is likely to be lifted form The Financial Times article written by Susanne Sternthal on January 16th, 2010. The FT article is well researched and, we assume, fact checked, citing Andrei Poyarkov (note the different transliteration) and Andrei Neuronov as primary sources. Both are published writers, and Poyarkov a respected scientist. Sternthal quotes Neuronov, who says that:
there are some 500 strays that live in the metro stations, especially during the colder months, but only about 20 have learned how to ride the trains. This happened gradually, first as a way to broaden their territory. Later, it became a way of life.
The number 20 appears to be a guesstimate, but the phenomenon of dogs riding the Moscow metro is documented extensively. There is even a website which collects photos and little anecdotes of the encounters at metrodog.ru. More photos can be found in this blog post, also a source for the image in the header. Video footage and reportage shot by ABC News in 2010, can be found here.
The earliest English language reference I could find is here, from 2007. In Russian, an article by N.N. Meshkova titled "Homeless Dogs in Moscow Metro" appeared in Biology bulletin #47, in 2000. Meshkova, who is a psychologist on the faculty of the Moscow State University, confirms the canine ability to take "goal-oriented subway rides." Having followed several individual dogs through the city, she observes one that rides back and forth from station to station begging for food, dogs that change trains to reach a specific destination, and dogs that visit the same above ground location regularly, using the subway (true commuting). In one instance, she writes:
A dog was observed riding from station "Lenin's Library" to "University" (5 stops, about 15 minutes), taking the central stairs and then an escalator to the street, where it headed to the nearby farmer's market. At the market, it approached the tent of a sausage vendor, and sat in front of it. The seller was not in, and so the dog, after waiting a few minutes, began to bark. A woman poked her head out from the adjacent tent, saw the dog, and said: "You came? Well, you'll have to wait. Lyuda (the name of the absent seller) will be back shortly." Having returned, the sausage vendor fed the dog and explained to the observer that it has been appearing regularly at this market for about half a year. (Translation mine.)
Finally, let me note that I personally saw lone dogs ride the subway in Moscow and in Bucharest on several occasions. It seemed to be a normal enough occurrence for people to ignore it completely.